第一章导论

组合数学主要学习内容

排列与组合（基础）
鸽巢原理（存在性）
生成排列和组合（生成算法）
二项式系数（组合数）
容斥原理（排列数）
递推关系和生成函法（重要）
特殊计数序列
图匹配、互异代表系统
Polya 计数

知识图

第二章排列与组合

2.1 基本计数原理

加法原理Addition Principle

乘法原理Multiplication Principle

减法原理 Subtraction Principle

减去不符合要求的

除法原理 Division Principle

2.2 集合的排列

集合的线性排列

n元素集合的r-排列——n个元素中取出r个元素有序摆放

全部r-排列数：$P(n,r)$

当$r>n$时$P(n,r)=0$

$P(n,r)=n!/(n-r)!$

$0!=1$

排列P(n,r)的递推关系

P(n, r)=n*P(n-1, r-1)
- 分步递归
- 选择1号盒子放一个球*从n-1个球中选r-1个放入r-1个盒子中
P(n, r)=P(n-1,r)+rP(n-1,r-1)
- 分类递推
- 不选第一个球+选了第一个球

组合模型

$C(n,r)=n!/((n-r)!*r!)$

$C(n,r)=C(n,n-r)$

$C(n,r)C(r,k)=C(n,k)C(n-k, r-k)$

先选出r个班委，再选出k个常委
等价于先选出k个常委，再选出r-k个其他班委

集合的多种类型排列

循环排列

n个元素集合的循环r排列个数为

$\frac {P(n,r)}r = \frac {n!}{r(n-r)!}$

n元素循环排列个数：(n-1)!

项链排列

即循环排列的一半即可

$\frac {P(n,r)}{2r} = \frac {n!}{2r(n-r)!}$

2.3 集合的组合

普通集合r-组合：$C(n,r)$

$\sum_{i=1}^nC_n^i=2^n$

2.4 多重集的排列

无限重复数

S有k种不同元素，每种元素都可以重复无限次，则S的r-排列个数为$k^r$

无限次可以放到每种元素个数都大于等于r

有限重复数

多重集排列

S＝{n1*a1, n2*a2,…, nk*ak}

$n_1+n_2+..+n_k=n$

S排列数为 $\frac {n!} {n_1!n_2!…n_k!}$

多重集排列的另一种解释

对n个元素集合划分为指定大小的多个部分(n个小球放入不同标号的若干个盒子中)

2.5 多重集组合

集合S有k种不同的元素，每种元素数量无限，r-组合数量

隔板法

相当于将r个元素分成k个不同区域
r个相同元素间插入k-1个隔板，分成k份
C(k+r-1，k-1) = C(k+r-1，r)
(k-1)+r个位置取出r个位置

两个整数解问题

$n_1+n_2+…+n_k=r$ 的非负整数解个数C(k+r-1, r)
$n_1+n_2+…+n_k=r$ 的正整数解个数 C(r-1, k-1)

第三章鸽巢原理

又称为抽屉原理，狄里克雷原理

3.1 鸽巢原理的简单形式

n+1个物体放进n个盒子中，至少有一个盒子包含两个或者更多的物体

中国剩余定理

令 m, n是互素的正整数，a和b分别是小于m和n的非负整数。

那么，存在正整数 x，使得 x 除以m余数为a, 且除以n余数为b，即 x＝pm+a，x =qn+b。

中国剩余定理一般形式

连续时间型问题

某学生有37天来完成一个课外科技项目，而学生需要不超过60小时的课外时间，他还希望每天至少安排一小时。证明：无论如何安排工作时间（每天都是整数小时），都存在连续的若干天，在此期间他恰好工作了13个小时。

设到第n天已经工作的时间为$s_n$

则$1\leq s1 \leq s_2…\leq s{37} \leq 60$

且$14\leq s1+13 \leq s_2+13…\leq s{37}+13 \leq 73$

根据鸽巢原理，上述74个数中必有$1\leq i\leq j\leq 37$，使得$s_i+13 = s_j$

3.2 鸽巢原理的加强形式

令q1, q2 , …, qn为正整数。若将q1+q2+…+qn – n+1个物体被放进n个盒子内，那么，

或者第1个盒子至少含有q1个物体
或者第2个盒子至少含有q2个物体
…
或者第n个盒子至少含有qn个物体

3.3 Ramsey定理

引理

在6个人中

或者有3个人，他们中每两个人都互相认识；
或者有3个人，他们中的每两个人都彼此不认识。

n阶完全图

上述引理可以描述为，给图K6的任意边着红、蓝色，一定存在一个红色K3或者一个蓝色K3

即K6—>K3,K3

Ramsey定理

如果m ≥ 2及n ≥ 2是两个整数，则存在正整数p，使得$K_p\rightarrow K_m，K_n$

Ramsey数

使$K_p\rightarrow K_m,K_n$成立的最小整数p

第四章生成排列和组合

4.1 生成排列

递归生成算法

原理

先排好1~n-1的，然后再对每一种排列插入n

递归进行以上过程

例子

3 1 2

1 3 2

1 2 3

3 2 1

2 3 1

2 1 3

邻位对换算法

原理

生成{1, 2, …, n}的排列算法:

初始：；
while 存在活动整数时，do

(1) 求出最大的活动整数m
(2) 交换m和其箭头指向的相邻整数的位置
(3) 改变所有满足p>m的整数 p 的箭头方向。
不存在活动整数时，算法结束。

例子

1 2 3

1 3 2

3 1 2

3 2 1

2 3 1

2 1 3

4.2 排列中的逆序

排列的逆序

令$i_1 i_2 ,…, i_n$ 是集合$\begin{Bmatrix}{1, 2, …, n}\end{Bmatrix}$的一个排列，如果$0\leq k < l \leq n$, 且$i_k > i_l$ , 称数对（$i_k , i_l$）是排列的一个逆序。

逆序数

逆序数$a_j$是排列中先于整数j并大于j的整数个数，度量j的反序程度。

逆序列

$a_j$表示一个排列$i_1,i_2…i_n$中数$j$的逆序数，则$a_1,a_2…a_n$为排列$i_1,i_2…i_n$的逆序列

每个逆序列满足如下条件：

$\forall 1\leq i \leq n,0\leq a_i \leq n-i$ 特殊的，$i=n$时，$a_n=0$

对于任意一个满足上述条件的整数序列$b_1,b_2…b_n$都存在集合$\begin{Bmatrix}{1, 2, …, n}\end{Bmatrix}$的唯一一个排列的逆序列为$b_1b_2..b_n$

由一个逆序列构造一个排列

从最大数开始：先把最大数写上，从大到小一个个推理位置

也可以从最小数开始

奇排列、偶排列

逆序个数为奇数，逆序个数为偶数

$i_1i_2…i_n$的逆序列为$b_1b_2…b_n$，$k=b_1+b_2+..+b_n$为逆序数，可以通过k次交换相邻两个数转换为$12…n$

4.3 生成组合

n元集合$\begin{Bmatrix}{x_1, x_2, …, x_n}\end{Bmatrix}$的组合与长度为n的二进制数一一对应

只需要从小到大的顺序写出$0到2^n-1$所有数的二进制形式即可

算法2：反射Gray码序生成算法

4.4 生成r-组合算法

基于字典序的算法

第五章二项式系数

5.1 帕斯卡三角形

别称：杨辉三角、贾宪三角

Pascal公式：$Cn^k=C{n-1}^k+C_{n-1}^{k-1}$

证明：即不包含1的k子集个数和包含1的k子集个数之和

5.2 二项式定理

$(x+y)^n=\sum_{k=0}^nC_n^kx^{n-k}y^k$

二项式系数其他等式

$kCn^k=n*C^{k-1}{n-1}$

n个人中选k人组成球队，且其中一人为队长

$2^n=\sum_{k=0}^nC_n^k$

$\sum{k=0}^n(C_n^k)^2=C{2n}^n$

$\sum_{k=0}^n(-1)^kC_n^k=0$

$C_n^0+C_n^2+…=C_n^1+C_n^3+…=2^{n-1}$

5.3 二项式系数的单峰性

n为偶数

$C_n^0…>C_n^{n-1}>C^n_n$

n为奇数

$C_n^0…>C_n^{n-1}>C^n_n$

Sperner定理

令S是n个元素的集合, C 是S的子集的集合

若C中任意两个不同的子集都存在包含关系,则称C是S的一个链。
若C中任意一个子集都不包含在其他子集内，即任意两个不同的子集都不存在包含关系，则称C是S的一个反链。

反链个数最多为$C_n^{\lfloor \frac n 2 \rfloor}$

最大链

链与反链的关系

5.4 多项式定理

$(x_1+x_2+…+x_t)^n$

多项式系数

$n_1+n_2+…+n_t=n$

重数分别为$n_1,n_2,…,n_t$的t种不同类型物品多重集的排列数

5.5 牛顿二项式定理

第六章容斥原理及应用

6.1 容斥原理

6.2 带重复的组合

容斥原理在多重集组合中的作用

典型例题

例1

例2

6.3 错位排列

即每个位置i上的数字都不是i。

利用容斥原理，设i位置上数字是i为事件$A_i$

则$D_n=|\overline {A_1\cup A_2\cup…\cup A_n}|=|\overline {A_1}\cap \overline {A_2} \cap … \cap \overline {A_n}|=n!-C_n^1(n-1)!+…+(-1)^nC^n_n0!$

$=n!(1-\frac 1 {1!}+\frac 1 {2!}+…+(-1)^n*\frac 1 {n!})$

递推关系

6.4 带有禁止位置的排列

利用容斥原理即可

6.5 另一个禁止位置问题

6.6 莫比乌斯反演

第七章递推关系和生成函数

7.1 若干数列

等差、等比、斐波那契数列

7.2 生成函数

计算多重集组合数时使用

几个常见展开式

定义

一个数列确定了一个生成函数，反之，一个生成函数也可以确定一个数列

利用生成函数求解带有约束的多重集的组合个数

7.3 指数生成函数

计算多重集排列数时使用

展开式

定义

例题

7.4 求解线性齐次递推关系

定义

特征方程法

7.5 非齐次递推关系

一般非齐次递推关系的通解

即先将$b_n$抹去，算出齐次通解

再用齐次通解加上非齐次特解得到通解

一般非齐次特解需要猜测一个带参数的形式并代入原表达式计算各个参数值

最后根据初始条件确定齐次通解的常系数

第8章特殊计数序列

8.1 Catalan数

Catalan数列

把凸n+1多边形区域分成三角形区域的方法数

$Cn=\frac 1 {n+1} C{2n}^n(n=0,1,2…)$

$\frac {Cn} {C{n-1}}=\frac {4n-2} {n+1}$

$Cn=C_0C{n-1}+C1C{n-2}+…+C_{n-1}C_0$

8.2 差分序列和Stirling数

问题引入

差分递归定义

上述结论可用于求前n项和

$\sum{k=0}^n C_k^p=C{n+1}^{p+1}$

Stirling数

第一类斯特林数

$s(p,k)$

将p个物品排成k个非空的循环排列方法数

$s(n,1)=(n-1)!(n\ge 1)$

$s(n,n-1)=C_n^2(n\ge 1)$

$若1\leq k \leq p-1,则:s(p,k)=(p-1)s(p-1,k)+s(p-1,k-1)$

第二类斯特林数

$S(p,k)$

把 p个元素的集合划分到 k个不可区分的盒子且没有空盒子的划分的个数

$若1\leq k \leq p-1,则:S(p,k)=kS(p-1,k)+S(p-1,k-1)$

$S^#(p,k)$

把p元素划分到k个非空、可区分的盒子的划分数

Bell数

Bell数是将 p个元素的集合分成非空、不可区分的盒子的划分数(至少一个盒子，至多p个盒子)

8.3 分拆数

整数拆分的组合含义

把 $n$个无区别的球放入无区别的盒子的放法（各盒子中可放入$t$ 个球, $1≤t≤n$）

分拆的表示

$n=nan+(n-1)a{n-1}+…+2a_2+1a_1$

上述n的一个拆分记为: $\lambda=n^{a_n}…2^{a_2}1^{a_1}$

分拆的几何表示: Ferrers图

如10的拆分3+3+2+2 $3^22^2$记为：

● ● ●

● ●

共轭分拆

分拆的矩阵的转置称为共轭分拆

上述矩阵的共轭分拆为4+4+2 即$4^22^1$

● ● ● ●

● ●

自共轭分拆

和共轭分拆完全相同的分拆

例题

有3个1克砝码，2个2克砝码，2个4克砝码，问能称出几种重量？有几种方法？

$G(x)=(1+x+x^2+x^3)(1+x^2+x^4)(1+x^4+x^8)$

将每个括号内的x换成对应的$x_1,x_2,x_4$再展开就可以得到具体的每个重量的称重方法
计算出来后每一项的指数就是能称出的重量
系数就是对应方法数

第一章 导论