组合数学

参考资料

类型	公式	示例
排列	$P(n,k) = \frac{n!}{(n-k)!}$	5 人选 3 人排队: $P (5,3)=60$
组合	$C(n,k) = \frac{n!}{k!(n-k)!}$	5 人选 3 人: $C (5,3)=10$

排列与组合
排列(有序, 可重复): $n^r$
组合(无序, 可重复): $\binom{n+r-1}{r}$
多重集排列
若集合中有重复元素, 排列数为 $\frac{n!}{\prod_{i} (k_i!)}$, 其中 $k_i$ 为第 $i$ 类元素的重复次数
将 $n$ 个相同元素分为 $k$ 组, 每组大小为 $R_i$, 则分组方式为 $\frac{n!}{\prod_{i=1}^{k} (R_i!)}$ | 重复组合 | $C(n+k-1,k)$ | 3 种水果买 5 个: $C (7,5)=21$ |
字典序生成排列
比特串生成组合

对于递推关系: $$ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} $$

特征方程法
特征方程为: $r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0$
若特征根 $r_1, r_2, \ldots, r_k$ 互异, 通解为 $$ a_n = A_1 r_1^n + A_2 r_2^n + \cdots + A_k r_k^n $$
若存在重根(如二重根 $r$), 对应解为 $(A + Bn) r^n$

\[ a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k} + F(n) \]

$\(C_n = \frac undefined{n+1} C (2n,n)$\) 应用场景:

类型	定义	递推关系
第一类	$[n \atop k]$: $n$ 元 $k$ 轮换	$s(n,k) = s(n-1,k-1) + (n-1)s(n-1,k)$
第二类	${n \atop k}$: $n$ 元 $k$ 子集	$S(n,k) = S(n-1,k-1) + kS(n-1,k)$

二项式系数求和
$\sum_{r=0}^{n} \binom{n}{r} = 2^n$
奇数项和等于偶数项和: $\sum_{r \text{ odd}} \binom{n}{r} = \sum_{r \text{ even}} \binom{n}{r} = 2^{n-1}$
加权求和: $\sum_{r=0}^{n} 2^r \binom{n}{r} = 3^n$
帕斯卡恒等式
$\binom{n+1}{r} = \binom{n}{r} + \binom{n}{r-1}$
杨辉三角性质: $\binom{n+1}{r+1} = \sum_{j=r}^{n} \binom{j}{r} \quad (r \leq n)$

名称	公式
范德蒙德	$\sum_{k=0}^r C(m,k)C(n,r-k) = C(m+n,r)$
多项式定理	$(\sum x_i)^n = \sum \frac{n!}{\prod k_i!}\prod x_i^{k_i}$

类型	公式	示例
排列	\(P(n,k) = \frac{n!}{(n-k)!}\)	5 人选 3 人排队: \(P (5,3)=60\)
组合	\(C(n,k) = \frac{n!}{k!(n-k)!}\)	5 人选 3 人: \(C (5,3)=10\)

类型	定义	递推关系
第一类	\([n \atop k]\): \(n\) 元 \(k\) 轮换	\(s(n,k) = s(n-1,k-1) + (n-1)s(n-1,k)\)
第二类	\({n \atop k}\): \(n\) 元 \(k\) 子集	\(S(n,k) = S(n-1,k-1) + kS(n-1,k)\)

名称	公式
范德蒙德	\(\sum_{k=0}^r C(m,k)C(n,r-k) = C(m+n,r)\)
多项式定理	\((\sum x_i)^n = \sum \frac{n!}{\prod k_i!}\prod x_i^{k_i}\)