Combinatorics (组合数学)

写在前面

• 任课教师：杨国武、卢光辉
• 参考教材：《组合数学及其应用》，清华大学出版社

知识点总结

符号表

符号	含义
$\mathbb{N}$	自然数集合
$\times$	直积
$\mathbf{B}$	重集
$P(n,r)$	从n个元素取出r个的线排列
$C(n,r), \binom{n}{r}$	从n个元素取出r个的组合数
$F(n,r)$	从n个元素取出r个的重复组合数
$D(n)$	n个元素的错排数

第一章-排列、组合与二项式定理

1.1 加法原理与乘法原理

Theorem 1.1.1 加法规则：设$\mathbf{S}$为有限集合，如果$S_i \subseteq \mathbf{S}, \mathbf{S} = \bigcup_{i=1}^{m} S_i$，且$i \neq j$时，$S_i \cap S_j = \Phi$, 则有：

$$|\mathbf{S}=||\bigcup_{i=1}^{m} S_i|=\sum_{i=1}^{m}|S_i|$$

换言之，当我们要求一个集合里的事物个数，我们可以将这个集合划分为几个互不相交的子集，将每个子集里的事物个数相加。

Theorem 1.1.2 乘法规则：若$S_i,(i=1,2,...,m)$为有限集，且$S=S_1 \times S_2 \times ... \times S_m=\{(a_1,a_2,...,a_m)|a_i \in S_i,i=1,2,...,m\}$, 则有：

$$|\mathbf{S}| = |S_1 \times S_2 \times ... \times S_m| = \prod_{i=1}^{m} |s_i|$$

换言之，如果有i个互相独立的事件分别有$a_1,a_2,...,a_i$种方法产生，则同时产生这i个事件的方法数为$\prod_{i=1}^{m} |a_i|$. 定理1.2中的$\times$代表直积。

排列组合问题的分类

从排列的角度：计算事物的有序安排/选择数 OR 无序安排/选择数；

从组合的角度：不允许任何事物重复/允许事物重复

集合、重集的概念

Definition 1. 集合（略）

Definition 2. 重集：有重复元素的集合，一般形式为$\mathbf{B}=\{k_1 \cdot b_1, k_2 \cdot b_2,...,k_n \cdot b_n\}$,意为重集B中有$k_1$个$b_1$,$k_2$个$b_2$,…以此类推。

1.2 排列

排列问题可以分为：线排列、圆排列、重排列。如他们的名字一样，线排列即把元素排成一条线（首尾不重叠），圆排列即排成一个环（首尾重叠）、重排列涉及到如果对一个重集内的所有元素做排列。⚠️注意，排列问题是有先后之分的。

Definition 1.2.1: (线排列) 设集合$\mathbf{A} = \{a_1,a_2,...,a_n\}$. 从这n个元素中取出r个($r \leq n$),按照一定次序排列起来，称为集合$\mathbf{A}$的$r-$排列/$r-$有序子集。集合$\mathbf{A}$的$r-$排列的所有方法个数记为$P(n,r)$。

Theorem 1.2.1: 对于正整数$n, r, r \leq n$,有:

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

Corollary: 当$n \geq r \geq 2$时，有：

$$P(n,r) = nP(n-1,r-1) = rP(n-1,r-1) + P(n-1,r)$$

证明思路：在 $n$ 个元素中取出并按顺序排成 $r$ 个（即 $P(n,r)$）——我们对一个“特别元素”（比如第 $n$ 个）是否被选用进行分类。

1. 情形 A：特别元素被选用

   • 它必须放在这 $r$ 个位置中的某一个：有 $r$ 种放置方式；
   • 剩下 $r-1$ 个位置由其余 $n-1$ 个元素按顺序填充：有 $P(n-1,r-1)$ 种；
   • 合计：$r\cdot P(n-1,r-1)$。

2. 情形 B：特别元素未被选用

   • 全部 $r$ 个位置都从其余 $n-1$ 个元素里产生：有 $P(n-1,r)$ 种。

两类互斥且穷尽，因此

$$P(n,r)=\underbrace{r\,P(n-1,r-1)}_{\text{选用特别元素}}+\underbrace{P(n-1,r)}_{\text{不选特别元素}}.$$

证毕。

题型总结：

1. 常规题型，直接利用集合$\mathbf{A}$的$r-$排列定义计算
2. 捆绑元素，要求一个元素紧跟另一个的前/后/某一特定位置, 或者逆向思维两个元素要求不满足XX条件。

Definition 1.2.2: (圆排列) 设集合$\mathbf{A} = \{a_1,a_2,...,a_n\}$. 从这n个元素中取出r个($r \leq n$),按照一定次序排列成一个圆圈（顺时针/逆时针），称为集合$\mathbf{A}$的圆排列/循环排列。

Theorem 1.2.2: 对于正整数$n, r, r \leq n$,其圆排列的个数为:

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

---

Definition 1.2.3: (重排列) 设重集$\mathbf{B} = \{k_1 \cdot a_1,k_2 \cdot a_2,...,k_n \cdot a_n\}$. 从这些元素中取出r个($r \leq n$),按照一定次序排列，称重集$\mathbf{B}$的$r-$排列为重排列。

Theorem 1.2.3: 重集$\mathbf{B} = \{\infty \cdot a_1,\infty \cdot a_2,...,\infty \cdot a_n\}$的$r-$排列个数为$n^r$.

Theorem 1.2.4: 重集$\mathbf{B} = \{k_1 \cdot a_1,k_2 \cdot a_2,...,k_n \cdot a_n\}$的全排列个数为$\frac{(k_1 + k_2 + ... + k_n)!}{k_1! k_2!...k_n!}$.

证明思路：要算全排列的个数，先看重集$\mathbf{B}$有多少个元素（共有$(k_1 + k_2 + \dots + k_n)$个），如果把这个集合当做一个普通集合，那么全排列一共有$n!$个。又因为对于重集里的每一个组($k_i \cdot n_i$),都有$n_i$种排列方式，相当于每一种都多算了这么多，所以要去掉这些重复的。

1.3 组合

Definition 1.3.1: 设$A=\{a_1,a_2,...,a_n\}$是具有$n$个元素的集合，$r$是非负整数。从这$n$个不同的元素里取$r$个不考虑次序组合起来$(r≤n)$，称为集合$A$的$r$-组合/$r$-无序子集。 记为$C(n,r)$.

THeorem 1.3.1: 对于$r \leq n, C(n,r)=\frac{P(n,r)}{r!} = \frac{n!}{r!(n-r)!}$

Proof: 从$n$个不相同的元素里取$r$个元素的组合个数为$C(n,r)$。而$r$个元素可以组成$r!$个$r$-排列,即$r!C(n,r)=P(n,r)$

Corollary 1: $C(n,r)=C(n,n-r), C(n,0)=C(n,n)=1$

从n个不同的元素中选出r个元素，就有n-r个元素没有被选出。因此选出r个元素的方式数等于选出n-r个元素的方式数.

Corollary 2 (Pascal’s Formula): $C(n,r)=C(n-1,r)+C(n-1,r-1)$

Proof:
$C(n,r)=\frac{n!}{r!(n-r)!} = \frac{n(n-1)!}{r!(n-r)!} = [(n-r)+r] \frac{(n-1)!}{r!(n-r)!} = \frac{(n-r)(n-1)!}{r!(n-r)!} + \frac{r(n-1)!}{r!(n-r)!}=\frac{(n-1)!}{r!(n-1-r)!}+\frac{(n-1)!}{(r-1)!((n-1)-(r-1))!} = C(n-1,r) + C(n-1,r-1)$

题型总结：

1. 数的整除问题，通常需要素数分解再继续做，或者根据公因数分组然后再分类讨论。

Definition 1.3.2（重复组合）: 从重集$\mathbf{B}=\{k_1 \cdot b_1,k_2 \cdot b_2,...,k_n \cdot b_n\}$中选取$r$个元素不考虑次序组合起来，称为从$\mathbf{B}$中取$r$个元素的重复组合 $F(n,r)$

Theorem 1.3.2: $\mathbf{B}=\{\infty \cdot b1,\infty \cdot b2,...,\infty \cdot bn\}$的$r$组合数为$F(n,r)=C(n+r-1,r)$

Proof: 比较Tricky。要解决的是从n种元素中可重复的挑出来r个做组合，要明白，$\{b_1,b_1,b_2\}$和$\{b_2,b_1,b_1\}...$等取法是等价的。为转化问题，将$b_1,b_2,...,b_n$用数字代替，即$b_1 \rightarrow 1$, $b_2 \rightarrow 2$, …。整个集合就只有重复的1，2，3，…,n这些数。每一种取法就可以转化为一个非递减的数列：$c_1,c_2,...c_r$,其中满足$1 \leq c_1 \leq c_2 \leq...\leq c_r$.

令$d_i = c_i + i - 1$, 则有：

$$f:\quad \begin{matrix} 1 &\le C_1 &\le C_2 &\le &\cdots &\le C_r &\le n \\ &\downarrow {+0} &\qquad \downarrow {+1} &\qquad &\cdots &\qquad \downarrow {+(r-1)} \\ 1 &\le d_1 &< d_2 &< &\cdots &< d_r &\le n + r - 1 . \end{matrix}$$

f是一个唯一的映射关系，而第一个数列中间是小于等于（可重复），第二个数列中间是小于（不可重复）。所以问题转化为了“从1到n-r+1，选出不重复的r个数的组合个数”问题，即$C(n-r+1,r)$

在Theorem 1.3.2中，如果B的不同元素的重复数至少是r，则结论仍成立。

题型总结：

1. 多元方程的非负整数解：对于每个满足方程$x_1+x_2+...+x_n=r$的非负整数解$x_1，x_2，...，x_n$都对应于重集B的一个r-组合。于是，方程$x_1+x_2+...+x_n=r$的非负整数解的个数就等于重集$\mathbf{B}=\{\infty \cdot b_1, \}$的r-组合数。

1.4 二项式定理

Definition 1.4.1: 当$n$是一个正整数时对任何$x$和$y$，有 $$(x + y)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k y^{n - k}$$

Corollary: (二项式系数的相关性质)

1. $(x + y)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k y^{n - k} = \sum_{k = 0}^{n} \binom{n}{k} x^{n-k} y^{k} = \sum_{k = 0}^{n} \binom{n}{n-k} x^{n-k} y^{k}$
2. (在1.的基础上，若$y=1$,) $(1+x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k$
3. (在1.&2.的基础上，若$x=1$,) $\sum_{k = 0}^{n} \binom{n}{k} = 2^n$；另一种表述：在具有n个元素的集合中，所有子集的个数为$2^n$
4. (在1.&2.的基础上，若$x=-1$,) 当n为正整数，$\sum_{k = 0}^{n} \binom{n}{k} {(-1)}^k = 0$； 另一种表述：在具有$n(n≠0)$个元素的集合中，偶数子集的个数与奇数子集的个数相等。

Definition 1.4.2 (广义二项式系数): 对于任何实数α和整数k，有

$$\binom{\alpha}{k} =\begin{cases} \dfrac{\alpha (\alpha - 1) \cdots (\alpha - k + 1)}{k!}, & k > 0, \\[1em] 1, & k = 0, \\[0.5em] 0, & k < 0. \end{cases}$$

对于满足 $|\frac{x}{y}| \lt 1$的所有x和y有 $(x + y)^\alpha = \sum_{k = 0}^{\infty} \binom{\alpha}{k} x^k y^{\alpha - k}$ (牛顿二项式定理)

Corollary: (广义二项式系数的相关性质)

1. 令$z = \frac{x}{y}, |z|<1$, $(1+z)^\alpha = \sum_{k = 0}^{\infty} \binom{\alpha}{k} z^k$
2. (在1.的基础上，令$\alpha=-n$) $(1+z)^{-n} = \frac{1}{(1+z)^{n}} = \sum_{k = 0}^{\infty} (-1)^k \binom{n+k-1}{k} z^k$
3. (在2.的基础上，令$n=1$) $(1+z)^{-n} = \frac{1}{(1+z)^{n}} = \sum_{k = 0}^{\infty} (-1)^k z^k$
4. (在3.的基础上，令$z=-z$) $(1-z)^{-n} = \frac{1}{(1-z)^{n}} = \sum_{k = 0}^{\infty} z^k$
5. (在1.的基础上，令$\alpha=\frac{1}{2}$) $(1+z)^{\frac{1}{2}} = \sqrt{(1+z)} = \sum_{k = 0}^{\infty} \binom{\frac{1}{2}}{k} z^k = 1+\sum_{k = 1}^{\infty} \frac{\frac{1}{2}(\frac{1}{2}-1)...(\frac{1}{2}-k+1)}{k!} z^k = 1+\sum_{k = 1}^{\infty} \frac{(-1)^{k-1}(2k-3)!!}{2^k k!} z^k = 1 + \sum_{k = 1}^{\infty} \frac{(-1)^{k-1}(2k-2)!}{2^k 2^{k-1} (k-1)! k!} z^k = 1 + \sum_{k = 1}^{\infty} \frac{(-1)^{k-1}}{2^{2k-1}} \frac{(2k-2)!}{k(k-1)!(k-1)!} z^k = 1+\sum_{k = 1}^{\infty} \frac{(-1)^{k-1}}{2^{2k-1}k} \binom{2k-2}{k-1} z^k$
6. (在1.的基础上，令$z=-rz$, 其中$r$为非零常数) 当$|-rz| \lt 1$,即$|z| \lt \frac{1}{r}$时, $(1-rz)^{-n} = \sum_{k = 0}^{\infty} r^k z^k$.

1.5 组合恒等式

恒等式1: 对于正整数n和k有：

$$\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$$

恒等式2: 对于正整数n, 有：

$$\sum_{k=1}^{n} k \binom{n}{k} = 2^{n-1}n$$

恒等式3: 对于正整数n, 有：

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

证明：由二项式公式微分证明：已知1.4.1 Corollary 2得：$(1+x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k$, 两边对$x$取微分，得到$n(1+x)^{n-1}=\sum_{k=1}^{n} \binom{n}{k} k x^{k-1}$。再令$x=-1$即可得证。

恒等式4: 对于正整数n, 有：

$$\sum_{k=1}^{n} k^2 \binom{n}{k} = 2^{n-2}n(n+1)$$

证明：依然二项式公式微分证明：已知1.4.1 Corollary 2得：$(1+x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k$, 两边对$x$取微分，得到$n(1+x)^{n-1}=\sum_{k=1}^{n} \binom{n}{k} k x^{k-1}$。再将两边乘以$x$再求微分（因为要凑出来$k^2$而不要$k(k-1)$）,得$n(1+x)^{n-2}(nx+1) = \sum_{k=0}^{n} \binom{n}{k} k^2 x^{k-1}$, 再令$x=1$即可得证。

恒等式5: 对于正整数n, 有：

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

证明同恒等式4，只需要最后一步令$x=-1$即可得证。

恒等式6: 对于正整数n, 有：

$$\sum_{k=0}^{n} \frac{1}{k+1} \binom{n}{k} = \frac{2^{n+1}-1}{n+1}$$

证明：与恒等式4，5不同，这一条为凑出$\frac{1}{k+1}$要采用积分的方式，两边同时对x做0-1定积分，得$\int_{0}^{1} (1+x)^n \, dx = \sum_{k=0}^{n} \binom{n}{k} \int_{0}^{1} x^k \, dx$, $\frac{(1+x)^{n+1}}{n+1} \Bigg|_{0}^{1} = \sum_{k=0}^{n} \binom{n}{k} \frac{x^{k+1}}{k+1} \Bigg|_{0}^{1}$, 代入得证。

恒等式7:(Vandermonde恒等式)对于正整数$n$,$m$和$p$,$p\leq min\{m,n\}$有

$$\sum_{k=0}^{n} \binom{n}{k} \binom{m}{p-k}=\binom{m+n}{p}$$

证明：因为有$(1+x)^m = \sum_{k=0}^{m} \binom{m}{k} x^k, (1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k, (1+x)^{m+n} = \sum_{k=0}^{m+n} \binom{m+n}{k} x^k$, 因此有$[\sum_{k=0}^{n} \binom{n}{k}x^k][\sum_{r=0}^{m} \binom{m}{r}x^r]=\sum_{j=0}^{m+n} \binom{m+n}{j} x^j$, 两边都取$x^p$的系数，即左边令$k+r=p$, 右边令$j=p$即可得证。

恒等式8: 对于正整数$n$,$m$，有：

$$\sum_{k=0}^{n} \binom{n}{k} \binom{m}{k}=\binom{m+n}{m}$$

证明：在恒等式7的基础上令p=m即可。

恒等式9: 对于正整数$n$，有：

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

证明：在恒等式8的基础上令m=n即可。

恒等式10: 对于非负整数$p,q,n$，有：

$$\sum_{k=0}^{p} \binom{p}{k} \binom{q}{k} \binom{n+k}{p+q}=\binom{n}{p} \binom{n}{q}$$

证明：

恒等式11: 对于非负整数$p,q,n$，有：

$$\sum_{k=0}^{p} \binom{p}{k} \binom{q}{k} \binom{n+p+q-k}{p+q}=\binom{n+p}{p} \binom{n+q}{q}$$

恒等式12: 对于非负整数$k,n$，有：

$$\sum_{i=0}^{n} \binom{i}{k} =\binom{n+1}{k+1}$$

证明：归纳法+Pascal公式

恒等式13: 对于所有实数$\alpha$和$k$, 有：

$$\sum_{j=0}^{k} \binom{\alpha+j}{j} = \binom{\alpha+k+1}{k}$$

证明：不断使用Pascal公式

证明方法归纳：

1. 数学归纳法
2. 利用二项式系数的公式，尤其是Pascal公式
3. 比较级数展开式的系数（二项式定理&母函数）
4. 积分微分
5. 组合分析

第二章 容斥原理

2.1 容斥原理基本概念

容斥原理是一种用间接计算来实现直接计算的思想，多数情况是问题本身很复杂，但是求解其补集较为简单。设集合$\mathbf{A}$是有限集合$\mathbf{S}$的子集，则计算$\mathbf{A}$中元素的个数等于$\mathbf{S}$中元素的个数再减去属于$\mathbf{S}$但又不属于$\mathbf{A}$的元素个数, 即

$$|\mathbf{A}| = |\mathbf{S}| - |\mathbf{\bar{A}}|，|\mathbf{\bar{A}}| = |\mathbf{S}| - |\mathbf{A}|$$

推广到两个集合$\mathbf{A_1}, \mathbf{A_2} \in \mathbf{S}$, 有：

$$|\mathbf{A_1} \cup \mathbf{A_2}| = |\mathbf{A_1}|+|\mathbf{A_2}| = |\mathbf{A_1} \cap \mathbf{A_2}|$$

$$|\bar{\mathbf{A_1}} \cap \bar{\mathbf{A_2}}| = |\mathbf{S}| - |\mathbf{A_1}| - |\mathbf{A_2}| + |\mathbf{A_1} \cap \mathbf{A_2}|$$

补充：对偶律：$\overline{\mathbf{A} \cup \mathbf{B} \cup \dots} = \overline{\mathbf{A}} \cap \overline{\mathbf{B}} \cap \dots$

Definition 2.1.1: 一般地，令 $A_i (i = 1, 2, \cdots, m) \subseteq S$，且 $A_i$ 是 $S$ 中具有性质 $p_i$ 的元素所组成的子集合。则$\bigcap_{i=1}^m A_i$是 $S$ 中同时具有性质 $p_1, p_2, \cdots, p_m$ 的元素子集合，$\bigcap_{i=1}^m \overline{A_i}$是 $S$ 中既不具有性质 $p_1$，又不具有性质 $p_2, \cdots,$ 更不具有性质 $p_m$ 的元素的集合。于是
$S$ 中不具有性质 $p_1, p_2, \cdots, p_m$ 的元素个数为

$$|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_m}| = |S| - \sum_{i=1}^m |A_i| + \sum_{i \ne j} |A_i \cap A_j|- \sum_{i \ne j \ne k} |A_i \cap A_j \cap A_k| + \cdots + (-1)^m |A_1 \cap A_2 \cap \cdots \cap A_m|$$

式中，第二个和式取遍集合$\{(i, j) \mid i, j = 1, 2, \cdots, m; i \ne j\}$, 第三个和式取遍集合$\{(i, j, k) \mid i, j, k = 1, 2, \cdots, m; i \ne j \ne k\},$ 以此类推。

Corollary 2.1.1: 集合$S$中至少具有性质$p_1, p_2, ..., p_m$中的一个性质的元素个数为：

$$|A_1 \cup A_2 \cup \dots \cup A_m| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - ... + (-1)^{m+1}|A_1 \cap A_2 \cap ... \cap A_m|$$

证明，$|A_1 \cup A_2 \cup \dots \cup A_m| = |S| - |\overline{A_1 \cup A_2 \cup \dots \cup A_m}|$, 由对偶律得: $=|S| - |\overline{A_1} \cap \overline{A_2} \cap ... \cap \overline{A_m} |$

补充：欧拉函数$\phi(n)$: ⼩于$n$⼜和$n$互素的正整数的个数。

e.g. 求$\phi(n)$的值

对于任何一个大于1的正整数$n$，都可以进行素数分解：即$n = p_1 p_2 ... p_m$. 设$S=\{1,2,...,n\}$, $Q_i(i=1,2,...,m)$表示$S$中能被$p_i$整除这一性质，并令$A_i$为具有$Q_i$这一性质的整数的集合。则$\overline{A_i}$为不能被被$p_i$整除，即与n互素的数。$\phi(n) = \bigcap_{i=1}^{m}\overline{A_i}$

$$\phi(n) = \bigcap_{i=1}^{m}\overline{|A_i|} = |S| - \sum_{i=1}^m |A_i| + \sum_{i \ne j} |A_i \cap A_j|- \sum_{i \ne j \ne k} |A_i \cap A_j \cap A_k| + \cdots + (-1)^m |A_1 \cap A_2 \cap \cdots \cap A_m|$$

代入$|S| = n, |A_i| = \frac{n}{p_i} (i=1,2,\ldots,m), |A_i \cap A_j| = \frac{n}{p_i p_j} (i,j = 1,2,\ldots,m;\ i\ne j), |A_i \cap A_j \cap A_k|= \frac{n}{p_i p_j p_k}, |A_1 \cap A_2 \cap \cdots \cap A_m| = \frac{n}{p_1 p_2 \cdots p_m}$化简即可。

2.2 重集的r_组合

这一节主要在探讨给定一个重集B,当其中的元素具有任意给定的重复数时，怎样利用容斥原理求B的r-组合数。

Method: 如何计算一般重集$B=\{k_1 \cdot a_1, k_2 \cdot a_2, ... ,k_n \cdot a_n\}$的r-组合数
Step 1: 构造重集$B'=\{\infty \cdot a_1, \infty \cdot a_2, ... ,\infty \cdot a_n\}$
Step 2: 计算重集$B'$的r-组合：$C_r = F(n,r)$
Step 3: 令$p_i$代表S中至少包含$k_i + 1$个$a_i$的性质，则$B$的r-组合就是$S$中不具有$p_i(i=1,2,3,...,n)$的个数。
Step 4: 由容斥原理得：$|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_m}| = |S| - \sum_{i=1}^m |A_i| + \sum_{i \ne j} |A_i \cap A_j|- \sum_{i \ne j \ne k} |A_i \cap A_j \cap A_k| + \cdots + (-1)^n |A_1 \cap A_2 \cap \cdots \cap A_n|$
其中$|A_1 \cap A_2 \cap \cdots \cap A_i|=F(n, r-(k_1 + 1) - (k_2 + 1) - ... - (k_i + 1))=F(n, r-(k_1 + k_2 + ... + k_i) - i)$;

2.3 错排问题

Definition 2.3.1 (错排问题的定义): 对于一个集合$A=\{a_1, a_2, ... , a_n\}$和集合$B=\{1,2,...,n\}$. 将两个集合中的元素一一配对，保证$\forall a_i \in A \And \forall j \in B,i \neq j$. 用$D_n$表示错排的个数。

Theorem 2.3.1 当$n \geq 1$, 有：

$$D_n = n!\left[ 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!} \right]$$

证明：利用容斥原理+全排列

由于 $e^{-1}$ 可以表示成下列的无穷级数$e^{-1} = 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!} + \cdots$, 故有：

$$e^{-1} = \frac{D_n}{n!} + (-1)^{\,n+1}\frac{1}{(n+1)!} + (-1)^{\,n+2}\frac{1}{(n+2)!} + \cdots,$$

于是有：$$\left|, e^{-1} - \frac{D_n}{n!} ,\right| < \frac{1}{(n+1)!}.$$

$$\lim_{n \to \infty} \frac{D_n}{n!} = e^{-1}.$$

即：错排个数与全排列个数之比约为$e^{-1}$

Theorem 2.3.2（错排数的递归形式）

$$D_n = (n-1)(D_{n-1}+D_{n-2})$$

2.4 相对位置上有限制的排列问题

Definition 2.3.1 (相对位置上有限制的排列问题的定义): 对于给定的正整数 $n$，计算集合 $\{1,2,\ldots,n\}$ 的且不允许出现 $12,23,34,\ldots,(n-1)n$ 的全排列的个数 $Q_n$。

Theorem 2.3.1: 对于 $n \ge 1$，有

$$Q_n = n! - \binom{n-1}{1}(n-1)! + \binom{n-1}{2}(n-2)! - \cdots + (-1)^{\,n-1} \binom{n-1}{\,n-1\,} 1!. \tag{2.9}$$

Theorem 2.3.2: (有限制排列与错排的关系) 当$n \geq 2$，有：

$$Q_n = D_n + D_{n-1}$$

2.5 一般有限制的排列问题

Definition 2.5.1 在一个给定的棋盘$C$上放入$k$个无区别棋子，每一个棋子占一格，要求各个棋子不同行不同列，级这些不同的放法为$r_k(C)$.

Definition 2.5.2 (棋盘多项式) 给定棋盘$C$，令$r_0(C)=1$, $n$为$C$的格子数，称

$$R(C) = \sum_{k=0}^{n} r_k(C) x^k$$

为棋盘多项式。

设C1=; C2=; C3=:

r₁( ) = 1, r₂( ) = 0； r₁( ) = 2, r₂( ) = 0； r₁( ) = 2, r₂( ) = 1

故有: $R(C_1) = 1+x; R(C_2) = 1+2x; R(C_3)=1+2x+x^2$

Theorem 2.5.1 给定棋盘$C$, 指定$C$中的某个格子$A$, 令 $C_i$ 为 $C$ 中删除指定格 $A$所在的⾏与列后所剩下的棋盘, $C_e$ 为 $C$ 中删除指定格 $A$ 后所剩下的棋盘，则有

$$r_k(C) = r_{k-1}(C_i) + r_k(C_e)$$

$$R(C) = x R(C_i) + R(C_e)$$

Definition 2.5.3 设$C_1$和$C_2$是两个棋盘，若$C_1$的所有格都不与$C_2$的所有格同行同列，则称两个棋盘是独立的。

Theorem 2.5.2: 若棋盘$C$可分解为两个独立的棋盘$C_1$和$C_2$，则有

$$R(C) = R(C_1)R(C_2)$$

Definition 2.5.4 (n元有禁位排列问题) 集合$\{1,2,…,n\}$的一个全排列且满足$i(i=1,2,…,n)$不排在某些已知位的不同的排列方式数。

Theorem 2.5.3: n元有禁位排列数为：

$$n!-r_1(n-1)!+r_2(n-2)!-\dots+(-1)^n r_n$$

其中$r_i$为i个棋子放入禁区棋盘的方式数。

第五章 鸽笼原理与Ramsey定理

有n只鸽子，飞进m(n>m)个鸽笼时，至少有一个鸽笼内有两只以上的鸽子 (或者还有别的名字：抽屉原理)

5.1 鸽笼原理的简单形式

Theorem 5.1.1 如果把$n+1$个物体放到$n$个盒子中去，则至少有一个盒子中放有两个或更多的物体。(反证法)

E.g. 1：在给定的$n$个整数$a_1, a_2, ... , a_n$中, 存在 $k$ 和 $l, (0 \leq k \lt l \leq n)$ 使得$a_{k+1} + a_{k+2} + ... +a_{l}$能被n整除。

Proof: 分类讨论
考虑$n$个和式：$a_1, a_1 + a_2, a_1 + a_2 + a_3, ... , a_1+a_2+...+a_n$

1. 这n个和中有一个能被n整除，结论成立
2. n个和式中一个都没有能被n整除的，则必然这些和式被n除时必然有$1,2,...,n-1$这样的余数。有n个和式、n-1种余数，则可以构造n-1个盒子，第i个盒子里放入被n整除余数为i的。由鸽笼原理易得必然存在$k,l(k \lt l)$使得$a_1+a_2+...+a_k$ 和 $a_1+a_2+...+a_l$具有相同的余数。即：

$$a_1 + a_2 + ... +a_k = bn+r$$

$$a_1 + a_2 + ... +a_l = cn+r$$

两式相减得：$$a_{k+1} + a_{k+2} + … +a_{l} = (c-b)n$$

5.2 鸽笼原理的一般形式

Theorem 5.2.1: 设$q_i$为正整数（$i = 1,2,3,...,n$），$q \geq q_1 + q_2 + ... + q_n - n + 1$, 如果把$q$个物体放入$n$个盒子中，必然存在一个$i$, 使得第$i$个盒子里至少有$q_i$个物体。（依然用反证法）

Corollary 1. 如果把$n(r-1) + 1$个物体放入$n$个盒子中，则至少存在一个盒子装有不少于$r$个物体。（在上面的定理中令$q_i = r$）

Corollary 2. 对于正整数$m_i(i = 1,2,3,...,n)$, 如果 $$\frac{\sum_{i=1}^{n}m_i}{n} \gt r - 1$$
则至少存在一个i, 使得$m_i \geq r$ (反证法：如果对于所有的$i$, 都有$m_i \lt r$…)

5.3 Ramsey 定理

Theorem 5.3.1: 在6个人中，一定有三个人相识，或者三个人不相识。

换一种说法：如果你画出任意 6 个点，并把每条边涂成实线或虚线，总能找到一个三角形，它要么全实线，要么全虚线。

证明：

1. 考虑这些人中的一个人（称为p）
2. 剩余人可以分成两个集合：1️⃣. F=与p相识的人的集合；和2️⃣. S=与p不相识的人的集合.
3. 由鸽笼原理得，这两个集合必定有一个集合包括至少3个人，分类讨论：如果F包含三个人，或者都不认识对方，或者有两人相识。可见，两种情况都使得定理成立。
4. 如果S包含三个人，则这三人或者都不认识对方，或者有两人不相识（注意，这里不用考虑都认识、两个人都相识的情况，因为只需要找到一种可能就行）。可见，这两种情况都能让定理成立，证毕。

Definition 5.3.1(Ramsey数): 设 $a,b$ 为正整数，令$R(a,b)$表示保证有$a$个人彼此相识或者有$b$个人彼此不相识所需要的最少人群人数。这个$R(a,b)$就是Ramsey数。

Theorem 5.3.2: Ramsey数的相关性质

1. $R(a,b) = R(b,a)$
2. $R(a,2) = a$
3. 当$a,b \geq 2$, $R(a,b)$是一个有限数，有

$$R(a,b) \leq R(a-1,b) + R(a,b-1)$$

4. 当$R(a-1,b)$ 和 $R(a,b-1)$都是偶数时，有

$$R(a,b) \leq R(a-1,b) + R(a,b-1)-1$$

5. $R(3,3)=6; R(3,4)=R(4,3)=9; R(3,5) = R(5,3) = 14$

Definition 5.3.2(另一种Ramsey数): 设用$r$种不同的颜色（$c_1, c_2, ..., c_r$）把一个完全$n$角形的边任意着色，令$R(a,b)$表示保证出现下列情形的数：
用$c_1$着色的一个完全$a_1$角形；用$c_2$着色的一个完全$a_2$角形；… 用$c_r$着色的一个完全$a_r$角形；称$R(a_1,a_2,...,a_r)$为Ramsey数。

Theorem 5.3.3: Ramsey数的相关性质拓展

1. 对于所有大于1的整数$a_1,a_2,a_3$, $R(a_1,a_2,a_3)$是存在的。
2. 对于任意正整数$m$和$a_1,a_2,...,a_m \geq 2$, $R(a_1,a_2,...,a_m)$是存在的。
3. 对于任意正整数$r$和$a_1,a_2,...,a_m \geq r$, $R(a_1,a_2,...,a_r)$是存在的。

第三章 母函数（发生函数/生成函数）

3.1 普通母函数

Def 3.1.1: 给定一个无穷序列$(a_1,a_2,...,a_n,...)$ (简记为$\{a_n\}$), 称函数 $$f(x)=a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n + \dots = \sum_{i=0}^{\infty} a_i x^i$$ 为序列$\{a_n\}$的普通母函数。

说明：变量$x$只是一种形式变元；普通母函数是一个无穷级数，没有必要去讨论它的收敛性, 只是序列的一种表达形式。换言之，序列与普通母函数一一对应。

普通母函数特别适用于包含组合数的序列，这是由于它具有牛顿二项式定理的形式。

Def 3.1.2: 给定一个无穷序列$\{a_n\}$, 称函数

$$f_e(x)=a_0 + a_1 \frac{x}{1!} + a_2 \frac{x^2}{2!} + \dots + a_n \frac{x^n}{n!} + \dots = \sum_{i=0}^{\infty} a_i \frac{x^i}{i!}$$

为序列$\{a_n\}$的指数母函数。

Thr 3.1.1: 设$f(x),f_e(x)$分别是序列$\{a_n\}$的普通母函数和指数母函数，则有 $$f(x) = \int_{0}^{\infty} e^{-s}f_e(sx)ds.$$

3.2 母函数的基本运算

Def 3.2.1 (普通母函数的加法、乘法运算): 设$A(x), B(x), C(x)$分别是序列$\{a_n\}, \{b_n\}, \{c_n\}$的普通母函数，则有 $$C(x) = A(x) + B(x),$$ 当且仅当$c_i = a_i + b_i (i=0,1,2,...)$; $$C(x) = A(x)B(x);$$ 当且仅当$c_i = \sum_{k=0}^{i}a_k b_{i-k}.$

Corollary:

1. 若$b_k = \sum_{i=0}^{k} a_i$, 则$B(x)=\frac{A(x)}{1-x}. \rightarrow \sum_{i=0}^{\infty} (1+i)x^i=\frac{1}{(1-x)^2}, \sum_{i=0}^{\infty} \frac{1}{2}(i+1)(i+2)x^i=\frac{1}{(1-x)^3}$
2. 若$b_k = \begin{cases}0, & k < l, \\ a_{k-l}, & k \ge l .\end{cases}$, 则$B(x)=x^l A(x)$
3. 若$b_k = a_{k + l}$, 则$B(x) = \frac{ A(x) - \sum_{k=0}^{\,l-1} a_k x^k }{ x^l }.$
4. 若$b_k = a_k + a_{k+1} + ... = \sum_{i=k}^{\infty} a_i$, 则$B(x) = \frac{A(1)-xA(x)}{1-x}$
5. 若$b_k = k a_k$, 则$B(x) = xA(x)$
6. 若$b_k = \frac{a_k}{1+k}$, 则$B(x) = \frac{1}{x} \int_{0}^{x}A(x)dx$

Def 3.2.2 (指数母函数的加法、乘法运算): 设$A(x), B(x), C(x)$分别是序列$\{a_n\}, \{b_n\}, \{c_n\}$的指数母函数，则有

$$C(x) = A(x) + B(x)$$

当且仅当$c_i = a_i + b_i (i=0,1,2,...)$;

$$C(x) = A(x)B(x);$$

当且仅当$c_i = \sum_{k=0}^{i} \binom{i}{k} a_k b_{i-k}.$

3.3 母函数在排列、组合中的应用 （这部分多看例题）

情形1: 考虑有$a,b,c$三种不同的物体，从中任意选取一个象征性记为$a+b+c$, 从中任意选出两个记为$ab+bc+ca$, 从中任意选取三个记为$abc$, 于是有多项式$(1+ax)(1+bx)(1+cx) = 1+(a+b+c)x + (ab+bc+ca)x^2 + abc x^3$. x的幂指数就表示被选取的物体的个数，而对应的系数则表明了所有可能的选取方法. 从n个不同的物体中选其r个物体，其方法数为$(1+x)^n$多项式(即普通母函数)中$x^r$的系数$\binom{n}{r}$.

情形2: 从n个不同的物体中选取r个物体的排列数恰好是指数母函数中$\frac{x^r}{r!}$的系数。

3.4 整数的拆分与Ferrers图

一个整数的拆分是把整数分拆为若干个正整数部分。而这些部分的次序是无关紧要的，等价于把n个无区别的球分放在一些无区别的盒子中的一种方法。

Thr 3.4.1: 设$a,b,c$是大于0的正整数，则

$$\frac{1}{(1-x^a)(1-x^b)(1-x^c)\dots}$$

的级数展开式中$x^n$的系数等于把正整数$n$拆成$a,b,c,...$的和的总方法数（即正整数$n$的拆分数$P(n)$）

Corollary:
用$P_k (n)$表示n拆分成1,2,…，k的允许重复的方法数. $P_o(n)$表示n拆分成奇整数的方法数. $P_d(n)$表示n拆分成不同的整数的方法
数. $P_t(n)$表示n拆分成2的不同幂(即1，2，4，8，…)的方法数:

1. $P_k(n)$的普通母函数是$\frac{1}{(1-x)(1-x^2)...(1-x^k)}$
2. $P_o(n)$的普通母函数是$\frac{1}{(1-x)(1-x^3)(1-x^5)...}$

Thr 3.4.2: 设$a,b,c$均大于零，则$(1+x^a)(1+x^b)(1+x^c)$的级数展开式中$x^n$的系数代表把n拆分成a,b,c,…的和，且a,b,c,…最多只出现一次的方法数。

Corollary:

1. $P_d(n)$的普通母函数是$(1+x)(1+x^2)(1+x^3)(1+x^4)...$
2. $P_t(n)$的普通母函数是$(1+x)(1+x^2)(1+x^4)(1+x^8)...$

Thr 3.4.3: 对于正整数$n$, 有$$P_o(n) = P_d(n)$$即把n拆分成奇整数的和的方式数等于把n拆分成不相同的整数的和的方式数。

Thr 3.4.4: 对于正整数$n$, 有$$P_t(n) = 1$$即任何正整数都可唯一地用一个二进制数来表示，而一个二进制数又可唯一地表成2的幂的和。

Thr 3.4.5: 对于正整数$n$, 有$$P(n) \lt e^{3 \sqrt{n}}$$进一步改进，有如下近似计算：$$P(n) \approx \frac{1}{4 \sqrt{3}n} e^{\pi \sqrt{\frac{2}{3}}\sqrt{n}}$$

Def 3.4.1: Ferrers图:

n的一个拆分对应唯一的一个Ferrers图，反过来，一个Ferrers图又对应一个n的唯一拆分。

Thr 3,4,6: 正整数n拆分成m项的和的方式数等于n拆分成最大数为m的方式数.

Thr 3.4.7 正整数n拆分成最多不超过m个项的和的方式数等于n拆分成最大的数不超过m的方式数。

3.5 母函数在组合恒等式中的应用 (这一部分以题为主)

第四章 递归关系

4.1 递归关系的建立

Def 4.1.1 递归关系的定义：设$(a_0,a_1,...,a_r,...)$是一个序列，把该序列中的$a_r$和它前面的几个$a_i(0 \leq i \lt r)$关联起来的方程称做一个递归关系.

Hanoi塔的递归描述：n个大小不一的圆盘依半径的大小，从下而上的套在柱子A上。现要求将所有的圆盘从柱子A上全部转移到柱子C上，每次只允许从一根柱子上转移一个圆盘到另一根柱子上，且在转移过程中不允许出现大圆盘放在小圆盘上。试问要转移多少次才能将柱子A上的n个圆盘全部转移到柱子C上去?

$$\begin{aligned} a_n & = 2a_{n-1} + 1, n \geq 2; \\ a_0 &= 1 \end{aligned}$$

$$a_n = 2^n - 1$$

Fibonacci序列的递归描述：

$$\begin{aligned} F_n & = F_{n-1} + F_{n-2}, n \geq 2; \\ F_0 &= F_1 = 1 \end{aligned}$$

相关性质：
Corollary:

1. $\sum_{i=0}^{n} F_i = F_{n+2} - 1$
2. $\sum_{i=0}^{n} F_{2i-1} = F_{2n} - 1$
3. $\sum_{i=0}^{n} F_i^2 = F_{n}F_{n+1}$
4. $F_{n+1}F_{n-1} - F_{n}^2 = (-1)^{n+1}$

4.2 常系数线性齐次递归关系

Def 4.2.1: 序列$(a_0,a_1,...,a_r,...)$中相邻$k+1$的关系如果为：

$$a_n = b_1 a_{n-1} + b_2 a_{n-2} + \dots + b_k a_{n-k}, n \geq k, b_i \neq 0$$

则该关系称为序列$(a_0,a_1,...,a_r,...)$的K阶常系数线性齐次递归关系。

Def 4.2.2: 与Def 4.2.1中的递归关系相联系的方程：

$$x_k - b_1 x_{k-1} - b_2 x_{k-2} - \dots - b_k = 0$$

叫做上述递归关系式的特征方程，其根称为特征根。

特征根的两种情况：1️⃣无重根；2️⃣有重根。

1️⃣无重根

Thr 4.2.1: 若$q \neq 0$, $a_n = q^n$是递归关系式$a_n = b_1 a_{n-1} + b_2 a_{n-2} + \dots + b_k a_{n-k}$的解，当且仅当$q$是其特征方程的根。

Def 4.2.3: $a_0 = h_0, a_1 = h_1, \dots, a_{k-1} = h_{k-1}$为递归关系式$a_n = b_1 a_{n-1} + b_2 a_{n-2} + \dots + b_k a_{n-k}$的初始条件。

Thr 4.2.2: 若$q_1, q_2, ... , q_k$是递归关系式$a_n = b_1 a_{n-1} + b_2 a_{n-2} + \dots + b_k a_{n-k}$的特征根，$c_1, c_2, \dots, c_k$为常数，则

$$a_n = c_1 q_1^n + c_2 q_2^n + \dots +c_k q_k^n$$

是递归关系式的解。

Def 4.2.4: 若对于递归关系式$a_n = b_1 a_{n-1} + b_2 a_{n-2} + \dots + b_k a_{n-k}$的任意一个解$a_n$，都存在一组常数$c_1, c_2, ..., c_n$, 使得$a_n$可以表示为$a_n = c_1 q_1^n + c_2 q_2^n + \dots +c_k q_k^n$的形式，则$a_n = c_1 q_1^n + c_2 q_2^n + \dots +c_k q_k^n$是该递归式的通解。

Def 4.2.5: 复数特征根的通解形式：
设$x_1=\delta+i \omega, x_2=\delta-i \omega$为多项式的一对复根，则通解为：

$$a_n = A_1 (x_1)^n + A_2 (x_2)^n = A_1 (\delta + i\omega)^n + A_2 (\delta - i\omega)^n = c_1 \rho^n \cos n\theta + c_2 \rho^n \sin n\theta$$

$$\begin{aligned} \rho &= \sqrt{\delta^2 + \omega^2}, \quad \theta = \tan^{-1}(\omega/\delta) \\ c_1 &= A_1 + A_2, \quad c_2 = \mathrm{i}(A_1 - A_2) \end{aligned}$$

2️⃣有重根

Thr 4.2.3: 若序列的递归关系的特征方程式$x_k - b_1 x_{k-1} - b_2 x_{k-2} - \dots - b_k = 0$有一个$m$重根$q$, 则$q^n, nq^n, ... , n^{m-1}q^n$都是递归关系式的解。

Thr 4.2.4: 设$q_1,q_2,...,q_t$分别是特征方程的相异的$m_1,m_2,...,m_t$重根，且$\sum_{i=0}^{t} m_i = k$, 则

$$a_n=\sum_{i=1}^{t} \sum_{j=1}^{m_i} c_{ij} n^{j-1}q_i^n$$

是递归关系式的通解。

4.3 常系数线性非齐次递归关系

Def 4.3.1: 序列$(a_0,a_1,...,a_r,...)$中相邻$k+1$的关系如果为：

$$a_n = b_1 a_{n-1} + b_2 a_{n-2} + \dots + b_k a_{n-k}+f(n), n \geq k, b_i \neq 0, f(n) \neq 0$$

则该关系称为序列$(a_0,a_1,...,a_r,...)$的K阶常系数线性非齐次递归关系。

Thr 4.3.1: 若$\bar{a_n}$是一个K阶常系数线性非齐次递归关系的特解，而${a_n}^* = \sum_{i=1}^{k}c_i q_i^n$ 或 $= \sum_{i=1}^{t} \sum_{j=1}^{m_i}c_{ij}n^{j-1}q_i^n$是与之对应的齐次递归关系（令$f(x)=0$）的通解，则$a_n = \bar{a_n} + {a_n}^*$ 为这个非齐次递归关系的通解

一些特殊的非齐次递归关系：

f(n)是n的t次多项式

1. 1不是特征根：

特解：$\bar{a_n} = A_0 n^t + A_1 n^{t-1} + \dots + A_t$, $A_{\square}$为待定常数。

2. 1是m重特征根（$m \geq 1$）：

特解：$\bar{a_n} = (A_0 n^t + A_1 n^{t-1} + \dots + A_t)n^m$, $A_{\square}$为待定常数。

f(n)是$\beta^n$形式

1. $\beta$不是特征根：

特解：$\bar{a_n} = A \beta^n$, $A$为待定常数。

2. $\beta$是m重特征根（$m \geq 1$）：

特解：$\bar{a_n} = A n^m \beta^n$, $A$为待定常数。

4.4 迭代法与归纳法

适用于k较大时，k阶线性齐次递归关系的特征方程的次数较高的情况。

迭代法：反复应用递归关系式进行迭代

归纳法：先⽤初值条件求出前⼏项，并观察其规律；设n=k时，结论成立。则当n=k+1时，有。。。

4.5 母函数在递归关系中的应用

用于求解非线性递归关系和非常系数递归关系。主要步骤如下：

1. 用$f(x)$表示序列 $(a_1,a_2,...,a_n)$ 的普通母函数，即$f(x) = \sum_{n=0}^{\infty} a_n x^n$
2. 利用递归关系$a_n$的表达式与上述普通母函数的关系，将母函数表达式化为关于$f(x)$的方程(大多数情况是将递归关系$a_n$的表达式代入母函数右端)，即$g(f(x))=0$
3. 解出$f(x)$
4. 将$f(x)$的表达式展开成幂级数。即可求得$a_n$的初等表达式。

Catalan数：满足如下序列递归关系：

$$\begin{cases}a_n = \displaystyle \sum_{k=1}^{n-1} a_k a_{n-k}, & n \geqslant 2 \\ a_1 = 1, \quad a_2 = 1 \end{cases}$$

$$a_n = \frac{1}{n} \binom{2n-2}{n-1}$$

4.6 Stirling数

Def 4.6.1 第一类Stirling数: 令

$$[x]_n = x(x-1)\dots(x-n+1)$$

如果 $[x]_n = \sum_{k=0}^{n} S_1(n,k)x^k$, 则称$S_1(n,k)$为第一类Stirling数。当$n \lt k$时，$S_1(n,k)=0$。

Thr 4.6.1 第一类Stirling数满足如下递归关系：

$$\begin{cases}s_1(n+1, k) = s_1(n, k-1) - n s_1(n, k), & n \geqslant 0, k > 0 \\s_1(0, 0) = 1, \quad s_1(n, 0) = 0, & n > 0 \end{cases}$$

Def 4.6.2 第二类Stirling数: 如果 $x^n = \sum_{k=0}^{n} S_2(n,k)[x]_k$,则称$S_2(n,k)$为第二类Stirling数。当$n \lt k$时，$S_2(n,k)=0$

Thr 4.6.2 第二类Stirling数满足如下递归关系：

$$\begin{cases}s_2(n+1, k) = s_2(n, k-1) + k s_2(n, k), & n \geqslant 0, k > 0 \\s_2(0, 0) = 1, \quad s_1(n, 0) = 0, & n > 0 \end{cases}$$

Thr 4.6.3 第二类Stirling数涉及集合的划分。第二类Stirling数$S_2(n,k)$就是n个元素的集合划分为k个不相交的非空子集的方式数。

Thr 4.6.3 第二类Stirling数满足如下性质：

1. $S_2(n,n)=1$, $S_2(n,k) = 0, n \lt k \space \textbf{or} \space k = 0 \lt n$
2. $S_2(n,2)=2^{n-1} - 1$
3. $S_2(n,n-1) = \binom{n}{2}$

第二类Stirling数与下面定义的Bell数的关系：

Def 4.6.3 Bell数：$B_n = \sum_{k=0}^{n}s_2(n,k)$, 显然$B_0=1$

S2(n,k)就是n个元素的集合划分为k个不相交的非空子集合的方式数。于是Bell数Bn就是n个元素的集合划分为不相交的非空子集的方式数。

Thr 4.6.4 Bell数满足如下递归关系：

$$B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k$$