组合数学简介

组合数学

Combinatorics教材课程安排组合数学简介排列组合公式母函数递推关系容斥原理抽屉原理Polya计数组合数学简介组合数学也称为组合分析或组合学，按研究的对象归于离散数学家族。早在中国古代的洛书、河图中就有组合数学的思想。组合数学的历史渊源扎根于数学娱乐和游戏中。现代组合数学在纯粹和应用科学上都有重要的价值。组合数学与抽象代数、拓扑学、数学基础、图论、博弈论、线性规划以及许多其它领域都有联系。驳杂组合数学与计算机的相互促进关系。算法速度洛书、河图洛书、河图是以不同形状、个数的黑白点排列的图案，并有许多神秘的解释。研究内容组合数学与很多数学分支相交叉，因此很难对它下一个正式的定义。大体上说，组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。主要内容：把有限集合的元素按一定的规则进行安排。这种安排被考究地称为组态（Configuration）。解决的问题组态的存在性组态的枚举、分类和计数组态的构造组态的优化幻方幻方是最古老最流行的一个数学游戏之一。在中世纪时期曾存在与幻方相关的玄想，人们将幻方佩戴身上辟邪。本杰明·富兰克林就是一个幻方迷，他的论文中包含很多有趣的例子。问题：用n2个整数1,2,…,n2构造一个n×n矩阵，使每行、每列、对角线元素之和均相等。这个相等的和叫做幻和。幻方的问题对任意的正整数n，n阶幻方存在吗？对于某个正整数n，如果n阶幻方存在，有多少不同的形式？构造存在的n阶幻方。幻方一阶幻方二阶幻方不存在三阶幻方四阶幻方有880个结论：对任意n≥1，n≠2，均可构造一个n阶幻方。但构造方法复杂，不唯一。奇数阶幻方的构造较简单，偶数阶较复杂。幻方体n阶幻方体(magiccube)是以下述方式由整数1,2,…,n3构造一个n×n×n立方阵列，其在下述每一条直线上的n个元素的和s都是相同的：(i)平行于立方体一条边的直线；(ii)每个截面上的两条对角线；(iii)四条空间对角线。数s叫做幻方体的幻和。不存在2阶幻方体也不存在3阶幻方体证明不存在4阶幻方体要困难的多。一个8阶的幻方体在Cardner的一篇论文中给出。棋盘的覆盖问题用1×2格的骨牌覆盖8×8棋盘。(1)能否在棋盘上放置32个骨牌使之完全覆盖该棋盘？(2)若存在，则有多少种不同的完全覆盖？(3)去掉了两个对角处格子的残缺棋盘，问能否用31枚骨牌恰将其覆盖？棋盘的覆盖问题3×3棋盘能否用1×2的骨牌完美覆盖呢？m×n的棋盘满足什么条件时，能被1×2的骨牌完美覆盖呢？等价于分子生物学中的二聚物问题。Fischer在论文StatisticalMechanicsofDimersonaPlaneLattice中得出涉及三角函数的用来计算m×n棋盘不同完美覆盖数的更一般公式。对于m×n的棋盘，1×b骨牌(b牌,b-omino)的情形呢？b=1情形monomino单牌b=2情形更一般的情形？先给一个充分条件此条件是否必要呢？b是素数b不是素数结论：一张m行n列棋盘有一个b-牌的完美覆盖当且仅当b是m的一个因子或者b是n的一个因子。进一步问题：一张m行n列棋盘有一个b-牌的完美覆盖时，覆盖的方式有多少呢？棋盘的覆盖问题棋盘的覆盖问题问题：证明用形可以完全覆盖剪去任一小方格后得到的(2n×2n-1)形棋盘。Nim取子游戏Nim取子游戏是由两个人面对若干堆硬币（或石子）进行的游戏。设有k≥1堆硬币，各堆分别含有n1，n2，…，nk枚硬币。游戏的目的是选择最后剩下的硬币。游戏规则如下：1.两个游戏人交替进行游戏（游戏人I：第一个取子者；游戏人II：第二个取子者）；2.当轮到每个游戏人取子时，选择这些堆中的一堆，并从所选的堆中取走至少一枚硬币（游戏人可以取走他所选堆中的全部硬币）；3.当所有的堆都变成空堆时，最后取子的游戏人即为胜者。对应的组合问题是，确定游戏人I获胜还是游戏人II获胜，以及游戏人应该如何取子才能保证获胜（获胜策略）。Nim取子游戏一堆硬币的情况两堆硬币的情况两堆硬币数相同平衡两堆硬币数不同不平衡结论：平衡游戏，II按照I取子数量在另一堆中取子即可获胜；不平衡游戏，I从大堆中取走硬币使两堆数量相等，后I每次取子数量与II相同，I即可获胜。用二进制表示k堆情形：平衡与不平衡结论：游戏人II能够在平衡游戏中获胜，游戏人I能够在非平衡取子游戏中获胜。36军官问题设有分别来自6个军团共有6种不同军衔的36名军官，他们能否排成6×6的编队使得每行每列都有各种军衔的军官一名，并且每行每列上的不同军衔的6名军官还分别来自不同的军团？18世纪瑞士数学家欧拉提出36个序偶(i,j)(i=1,2,…,6,j=1,2,…,6)能否排成6×6阵列，使得每行和每列，这6个整数1,2,…,6都能以某种顺序出现在序偶第一个元素的位置上，并以某种顺序出现在第二个元素的位置上？是否存在这样的两个6×6矩阵，其元素取自1,2,…,6使得

i)整数1,2,…,6以某种顺序出现在矩阵的每一行和每一列；

ii)当这两个矩阵并置时，所有36个序偶(i,j)(i=1,2,…,6,j=1,2,…,6)全部出现？36军官问题3阶拉丁方：在矩阵每行和每列上，整数1,2和3中的每一个都出现一次。问题转化为：是否存在两个正交的6阶拉丁方？正交拉丁方对于n为奇数和4的倍数，欧拉指出了如何构造一对n阶正交拉丁方。欧拉猜想，不存在像6,10,14,18,…这样阶数的拉丁方。通过穷举法，Tarry在1901年证明了欧拉的猜想对n=6成立。大约在1960年前后，三位数理统计学家成功证明了欧拉猜想对于所有大于6的n都是不成立的。集合论集合中元素个数的定义（集合的势）一一对应的思想有限集无限集可数集(可列集)常见数集的势正偶数集与正整数集两个可数集的并仍为可数集可数个可数集的并仍为可数集自然数集与有理数集实数确实比自然数多四个基本的计数原理加法原理

做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，…，在第n类办法中有mn种不同的方法，那么完成这件事共有N=m1+m2+m3+…+mn种不同方法。乘法原理做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N=m1×m2×…×mn种不同的方法。减法原理除法原理例题137名运动员打乒乓球，单淘汰赛，问决出冠军需要打多少场比赛？方法一：方法二：例题n元集合的子集有多少个？加法原理乘法原理所有n长的0,1序列有多少个？例题求n元集合的含某固定元的子集的个数？设Sn={1,2,…,n}，求例题设A,B为有限集，。从A到B的映射有多少个？若m=n，则从A到B的双射有多少个？若m≤n，则从A到B的单射有多少个？若m≥n，则从A到B的满射有多少个？集合B上的幂等映射有多少个？集合B上的部分映射有