从广义上讲组合数学就是离散数学。

1.1 基本计数法则

加法法则

若 |A| = m , |B| = n , A⋂$\bigcap$B = ⊘$\oslash$ , 则 |A⋃$\bigcup$B| = m + n 。

乘法法则

若 |A| = m , |B| = n , AxB = {(a,b) | a ∈$\in$A,b ∈$\in$ B}, 则 |A x B| = m · n 。

【例】求小于10000的含1的正整数的个数。

• 小于10000的不含1的正整数可看做4位数,但0000除外
• 小于10000的不含1的正整数的个数有94−1=6560$9^4-1=6560$
• 小于10000的正整数的个数有104−1=9999${10}^4-1=9999$
• 小于10000的含1的正整数的个数：9999－6560=3439

【例】求小于10000的含0的正整数的个数

• 不含0的1位数有9个，2位数有92$9^2$个，3位数有93$9^3$个，4位数有94$9^4$个 ，共7380个
• 小于10000的含0的正整数的个数为：9999-7380=2619

1.2 一一对应

【例】n个人参加单淘汰赛，最后产生冠军的过程，需要多少场比赛？

• 比赛的台数和每一场淘汰一名选手一一对应

• 答案：n-1
  【例】求n2$n^2$个人站成n排的方案数

• 站成n排和站成1排一一对应

• 答案：n2!$n^2!$

【定理】带n个有标号1,2,…,n的顶点的树的数目等于nn−2$n^{n-2}$（n>=2）

1.3 排列与组合

排列的定义

设A={a1,a2,…,an}是n个不同的元素的集合，任取A中r个元素按顺序排成一列，称为从A中取r个的一个排列，其数目记为P(n,r) ，r满足0≤r≤n。
排列可以看作n个不同的元素取r个放进r个不同的盒子的放法.

• 从n个不同的球中取一个球放在第一个盒子中，
• 从余下的n-1个球中取一个球放在第二个盒子中，
• …………………………………
• 从余下的n-(r-1)个球中取一个放在第r个盒子中

根据乘法法则：
P(n,r)=n(n-1)…(n-r+1)=n!／(n-r)!
全排列：P(n,n)=n(n-1)…2×1=n!

组合的定义

当从n个不同元素中取出r个而不考虑它的顺序时,称为从n中取r个的组合,其数目记为C(n,r)。
因为组合不考虑顺序，所以组合数会比排列数少很多。
C(n,r)=P(n,r)/r! =n!/[r!(n-r)!]
C(n,r)=C(n,n-r)

圆周排列的定义

在排列中，如果我们不横排而是将各元素排列在一个圆周上，那么我们称这种排列方式为圆周排列。规定相对位置不变算同一个圆周排列。将从n中取r个作圆排列的排列数记作Q(n,r)。
在排列中1234,2341,3412,4123为四个不同的排列，而在圆周排列中这些排列是一个。
从n中取r个作排列，与圆排列相比，重复了r倍
Q(n,r)=P(n,r)/r
Q(n,r)=P(n,r)/r=n!/r(n-r)!
Q(n,n)=P(n,n)/n=n!/n=(n-1)!

【例】5对夫妇出席一宴会，围一圆桌而坐，试问有几种不同的方案？若要求每对夫妻相邻又有多少种方案?

• （1）Q(10，10)
• （2）Q(5，5）*25$2^5$

1.4 多重集的排列

设S是一个多重集，有K个不同类型的元素，各元素的重复分别为n1,n2,…,nk,n=n1+n2+…+nk,则多重集S的全排列数为:n!n1!n2!...nk!$\frac{n!}{n1!n2!...nk!}$

证明：由Cn1nCn2n−n1Cn3n−n1−n2...Cnkn−n1−n2−...−nk−1$C_n^{n1}{C}_{n-n1}^{n2}{C}_{n-n1-n2}^{n3}...C_{n-n1-n2-...-n_{k-1}}^{nk}$化简而得。

【例】求1040${10}^{40}$和2030${20}^{30}$的公因数的数目。

• 1040=240540${10}^{40}=2^{40}{5}^{40}$
• 2030=260530${20}^{30}=2^{60}{5}^{30}$
• 公因式形如2i5j（0≤i≤40,0≤j≤30）$2^i{5}^j（0\le i\le 40,0\le j\le 30）$
• 公因式数目41X31

【例】有n个不同的整数，从中取出两组来，要求第1组的最小数大于另一组的最大数，求满足条件的所有取法的数量。

• 只要从n个数中取出一组m个数(设m=a+b，2≤m≤n$2\le m\le n$),此时方案数为C(n,m)
• 将m个数从大到小取a个(a≥1$a\ge 1$)作为第一组,剩余的(剩下b个，b≥1$b\ge 1$)为第二组。从m个数中取第一组数共有m-1中取法。
• 答案：∑nm=2(m−1)C(n,m)$\sum _{m=2}^n(m-1)C(n,m)$

1.5 排列的生成算法

对于给定的字符集，用有效的方法将所有可能的排列无重复无遗漏地枚举出来。

序数法

【思想】n个元素的n!个全排列与n!个数一一对应。
【定理】令n≥0，0≤m≤n!−1$n\ge 0，0\le m\le n!-1$，则m可以唯一地表示为：
m=an−1(n−1)!+an−2(n−2)!+…+a1(1)!$m=a_{n-1}(n-1)!+a_{n-2}(n-2)!+\dots +a_1(1)!$
其中：0≤ai≤i,i=1,2,…,n−1$0\le a_i\le i,i=1,2,\dots ,n-1$。反之，任何满足上式的数m都是一个满足[0，n!-1]的数。

字典序法

【思想】对于n个字符（元素）的任何二个排列，我们都可以直接比较它的大小。
【步骤】
1. 从排列的末尾开始,逐步向前搜索,直到找到比其后面相邻的数小的数；
如果未找到,表明不再有下一个排列,程序终止;
2. 从该数后面的序列中寻找比该数大的最小的(最靠后的)数来替换它(使用交换);
3. 将余下的数反转。

【例】求排列839647521在字典序中的下一个排列。

• 找到前面数小于相邻后面数的最后一个，4
• 4与后面比它大但（位置最靠后）最小的数交换，5
• 此时5右边为7421，倒置为1247，即得下一个排列:839651247。

组合的生成算法

从1,2，…,n这n个元素中取出r个组合，用c1,c2,…,cr表示，
假定c1<c2<...<cr$c_1<c_2<...<c_r$，
那么cr≤n，cr−1≤n−1，...，c1≤n−r+1$c_r\le n，c_{r-1}\le n-1，...，c_1\le n-r+1$。
当存在cj<n−r+j$c_j<n-r+j$时，找出下标最大值设为i，从ci+1$c_i+1$替换ci$c_i$，
如果i<r$i<r$，再用ci+1=ci+1，ci+2=ci+1+1，...，cr=cr−1+1$c_{i+1}=c_i+1，c_{i+2}=c_{i+1}+1，...，c_r=c_{r-1}+1$
【例】从1,2,3,4,5,6中取3个的组合

• 456是最后一个
• 256在字典序中的下一个组合是345（ ci=2,2修改为3，后边两位改为4,5，得345）
• 345在字典序中的下一个组合是346（ ci=5,5修改为6，得346）

1.6 允许重复的组合

【定理】在n个不同的元素中取r个进行组合，若允许重复，则组合数为C(n+r-1,r)。
从n个不同元素中取r个作允许重复的一个组合<=>从n+r-1个不同元素中取r个作不允许重复的一个组合

【例】x1+x2+…+xn=b，n是正整数，b都是非负整数，求方程的非负整数的解的个数。

• 方程的非负整数的个数与b个无标志的球放进n个有区别的盒子的情况一一对应。
• 答案：C(n+b-1,b)

1.7 组合的解释

【例】路径数问题：如图从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，问有多少条路径。

• 无论怎样走法，在x方向上总共走m步，在y方向上总共走n步，若用一个字母x表示当前在x方向上走一步，一个字母y表示当前在y方向上走一步：
• (0,0)→(m,n)的每一条路径可表示为包含m个x与n个y的一个序列；
• 答案：C(m+n,m)=C(m+n,n)

【例】7位科学工作者从事一项机密的技术研究，他们的实验室门上挂有多把锁，每位参加该项工作的人都有若干把打开锁用的钥匙，为了安全起见，要保证必须有4人到场方可打开实验室的门（ 只有3人到场一定打不开，且4人到场一定可以打开），试问：
①门上至少要挂上多少把锁？(总共至少有多少把不同的钥匙？)
②每人至少需持几把钥匙？

• 第一问：每３人至少缺１把钥匙，每３人所缺钥匙必须不相同（反证法证明），答案：C(7，3)=35
• 第二问：任1人对于其他６人中的每３人，都至少有１把钥匙与之相配才能开锁，不存在有1人对于其他6人中的两组，都用一把钥匙相配这种情况（反证法证明），答案：C(6，3)=20