组合数学（1）

· · 个人记录

排列

将 n 个不同的元素，按照一定的顺序排列，称为从 n 个元素中选取 m 个元素的一个排列。

从 n 个不同的元素中取出 m 个不同元素，所有不同的排列个数称为排列数。

通过乘法原理可以得到排列数的计算公式：

A_n^m=P_n^m=\prod_{i=n-m+1}^{n}i=\frac{n!}{(n-m)!} \end{aligned}

全排列是排列数的一种特殊情况，n 个不同元素的全排列为 A_n^m=n!

组合

从 n 个不同的元素中取出 m 个不同的元素，不论顺序，合成一组，被称为从 n 个元素中不重复地选取 m 个元素的一个组合，所有组合的总数称为排列数。

在 A_n^m 中每一个长度为 m 的排列都会被计算 A_m^m 次，但它们本质相同，由此得到组合数的计算公式：

C_n^m=\frac{A_n^m}{A_m^m}=\frac{n!}{m!(n-m)!} \end{aligned}

组合恒等式

二项式定理

(a+b)^n=\sum_{i=0}^nC_n^ia^ib^{n-i} \end{aligned}

特别的，同理可得：

(1+x)^n=\sum_{i=0}^nC_n^ix^i \end{aligned}

其本质就是杨辉三角

基础恒等式

(1)$ $C_n^m=C_n^{n-m}

可以理解为从 n 个数中选取 m 个数的组合数，与从 n 个数中不选取 m 个数的组合数相等。

(2)$ $C_n^m=C_{n-1}^{m-1}+C_{n-1}^m

可以理解为从 n 个数中选取 m 个数的组合数与在 n-1 个数中已经选取了 m-1 个数，同时再将新加入的一个数补入各组合和再 n-1 个数中选取了 m 个数的各组合总数相等。

由二项式定理 (a+b)^n=\sum_{i=0}^nC_n^ia^ib^{n-i}

则 (1+1)^n=\sum_{i=0}^nC_n^i=2^n

可以理解为有 n 个 0/1 数，总共有 2^n 个状态，每个状态相当于在 n 个数中选取值为 1 的数。

由二项式定理可得，原式即为 (1-1)^n 特别的，当 n=0 时，有 0^0=1

(5)$ $\begin{aligned}\sum_{i=0}^{m}C_{n}^{i}C_{m}^{m-i}=C_{n+m}^{m}\end{aligned}

可以理解为从 n 个数中选取 i 个的方案数乘上在 m 个数中选取 m-i 个（本质上还是 i 个）的方案数，是一种类似于卷积的形式。

相当于分别从 n 个元素和 m 个元素中取 i 个元素的一个组合，各项之和就是所有选法。

(6)$ $\begin{aligned}\sum_{i=0}^{n}(C_n^i)^2=C_{2n}^{n}\end{aligned}

由 (5) n=m 即可推导。

(7)$ $\begin{aligned}\sum_{i=0}^niC_n^i=n2^{n-1}\end{aligned}

高斯消元。

(8)$ $\begin{aligned}\sum_{i=0}^ni^2C_{n}^i=n(n+1)2^{n-2}\end{aligned} (9)$ $C_{n}^{r}C_{r}^{k}=C_{n}^{k}C_{n-k}^{r-k}

可以理解为从 n 个数中选取 r 个，再从选出的 r 个数中选取 k 个的方案数。

等价于从 n 个数中选取 k 个再乘上重复数量。

(10)$ $\begin{aligned}\sum_{i=0}^{n}C_{i}^{k}=C_{n+1}^{k+1}\end{aligned}

先假定 n+1 个元素必选，剩下的组合数为 C_{n}^{k}，再假定第 n+1 个元素不选，剩下的方案数为 C_{n-1}^{k}，以此类推。

卡特兰数

卡特兰数的递推关系式：

C_n=\begin{cases}1&n\le2\\ \sum_{i=0}^nC_iC_{n-i}&n\ge2\end{cases}

卡特兰数的计算公式：

C_n=C_{2n}^n-C_{2n}^{n+1}=\frac{C_{2n}^n}{n+1}

卡特兰数满足以下性质：

  5. 凸多边形划分

斯特林数

第一类斯特林数

圆排列是排列的一种，但是圆排列是一个环，两个圆排列不同当且仅当这两个圆排列上的数不能通过转置而对应相同。

从 n 个数中取 m 个的圆排列个数为：

Q_n^m=\frac{A_n^m}{m}=\frac{n!}{m\times(n-m)!} \end{aligned}

第一类斯特林数是指将 n 个数的排列划分为 m 个圆排列的本质不同的划分方法。

\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}

解释：在 n 个数的排列划分为 m 个圆排列划分方法等于在已经有 n-1 个数划分为 m-1 个圆排列中单独加入一个只有一个数的圆排列的种数加上将这个数加入有 n-1 个数 m 个圆排列中的任意两个数之间的种数之和。

第二类斯特林数

第二类斯特林数时集合的拆分，将 n 个数的排列拆分成 m 个集合的方案数。

递推公式为：

\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}

解释：在 n 个数划分为 m 个集合的方案数等于将这个数新建立一个集合的方案数加上将这个数加入任何一个集合的方案数。

一些 基础的 斯特林恒等式

\begin{aligned}\sum_{i=m}^{n}C_{i}^{m}\begin{bmatrix}n\\i\end{bmatrix}=\begin{bmatrix}n+1\\m+1\end{bmatrix}(m\le{n})\end{aligned} \begin{aligned}\sum_{i=m}^{n}C_{i}^{n}\begin{Bmatrix}i\\m\end{Bmatrix}=\begin{Bmatrix}n+1\\m+1\end{Bmatrix}(m\le{n})\end{aligned} \begin{aligned}\sum_{i=0}^m(n+i)\begin{bmatrix}n+i\\i\end{bmatrix}=\begin{bmatrix}n+m+1\\m\end{bmatrix}\end{aligned} \begin{aligned}\sum_{i=0}^mi\begin{Bmatrix}n+i\\i\end{Bmatrix}=\begin{Bmatrix}n+m+1\\m\end{Bmatrix}\end{aligned} \begin{aligned}\sum_{i=m}^n\begin{bmatrix}i\\m\end{bmatrix}\begin{Bmatrix}n+1\\i+1\end{Bmatrix}(-1)^{m-i}=C_{n}^{m}(m\le{n})\end{aligned} \begin{aligned}\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}=n!\end{aligned}

不相邻的排列

从 1-n 的数中选出 k 个不同元素，并且如果选择了 a ，那么 a+1 就不能选择，求出不同的方案数量。

假如选择的数从小到大为 a_1,a_2,a_3,...a_k ，对于任意的 i\in[i,n) 要满足 a_i+1\not=a_{i+1} 所以可以在选择 a_i 的同时把 a_i+1 拿走，也就是忽略掉 a_i+1 ，这样没有被忽略的数的个数就变成了 n-k+1 ，所以答案就是 C_{n-k+1}^{k}

错位排列

一个错位排列就是指对于任意的 a_i\not=i

求出有多少个不同的长度为 n 的排列是错位排列。设 d_i 为 i 个不同元素的错位排列方案数，对于 d_i 的计算分为两种：

  1. 前 i-1 个位置满足错位排列，那么第 i 个位置只需要和前面任意一个位置交换即可，产生的贡献为 (i-1)d_{i-1}
  2. 前 i-1 个位置恰好只有 i-2 个位置满足错位排列，那么第 i 个数就必须和这个位置交换，所以产生的贡献为 (i-1)d_{i-2}

得到错位排列的递推式：

d_i=\begin{cases}0&(i=1)\\1&(i=2)\\(i-1)(d_{i-1}+d_{i-2})&(2<i)\end{cases}

多重集的排列数

S=\{n_1\times{a_1},n_2\times{a_2},n_3\times{a_3},...n_k\times{a_k}\}$，表示 $S$ 中存在 $n_1$ 个 $a_1$ ，$n_2$ 个 $a_2

多重集 S 的排列数为：

\begin{aligned}\begin{pmatrix}\sum_{i=1}^kn_i\\n_1,n_2,...n_k\end{pmatrix}\frac{(\sum_{i=1}^kn_i)!}{\prod_{i=1}^kn_i!}\end{aligned}

证明：(\sum_{i=1}^kn_i)! ，对于每一种方案在上式中都会有 \prod_{i=1}^kn_i! 的贡献，所以要把这部分除去。

对于正常的组合数 C_n^m 相当于有两种元素，分别表示选或者不选，其中选择的元素有 m 个，不选的元素有 n-m 个，所以可以得到：

\begin{pmatrix}n\\m\end{pmatrix}=\begin{pmatrix}n\\m,n-m\end{pmatrix}