组合数学与计数

笔记，不含练习。

基本计数原理

加法原理
乘法原理

组合数

\(\binom{n}{r}\) 或 \(C_{n}^{r}\) 表示组合数，从 \(n\) 个元素中选 \(r\) 个的方案数，不考虑顺序。\(\binom{n}{r}=C_n^r=\frac{n!}{r!(n-r)!}\)。

类似的，\(A_{n}^{r}\) 表示排列数，从 \(n\) 个元素中选择 \(r\) 个的方案数，考虑顺序。\(A_n^r=\frac{n!}{(n-r)!}\)。

一些性质

对称恒等式

\[\binom{n}{k}=\binom{n}{n-k} \]

吸收提取不等式

\[\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1} \]

与下降幂结合

\[\binom{n}{k}\times k^{\underline{m}}=\binom{n-m}{k-m}\times n^{\underline{m}} \]

加法归纳恒等式

\[\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} \]

二项式定理

\[(x+y)^n=\sum_k\binom{n}{k}x^ky^{r-k} \]

插板法

现有 \(n\) 个完全相同的元素，要求将其分为 \(k\) 组，保证每组至少有一个元素，一共有多少种分法？

考虑拿 \(k-1\) 块板子插入到 \(n\) 个元素两两形成的 \(n-1\) 个空里面。
因为元素是完全相同的，所以答案就是 \(\binom{n-1}{k-1}\)。
本质是求 \(k\) 个未知数和为 \(n\) 的正整数解的组数。

允许每组为空？

考虑加入 \(k-1\) 个元素，这样有 \(n+k-1\) 个元素。考虑从中选 \(k-1\) 个作为板子进行分隔。
答案即为 \(\binom{n+k-1}{k-1}\)。
本质是求 \(k\) 个未知数和为 \(n\) 的非负整数解的组数。

如果再扩展一步，要求对于第 \(i\) 组，至少要分到 \(a_i\)，\(\sum a_i\le n\) 个元素呢？

考虑先把下界补满，然后问题就转换为允许每组为空的了。
答案即为 \(\binom{n-\sum a_i+k-1}{k-1}\)。

二项式求导

计算 \(\sum_{k=1}^nk^2\binom{n}{k}\)。

考虑 \(ax^n\) 的导数等于 \(anx^{n-1}\)。

由二项式定理得：

\[(1+x)^n=\sum_{k=0}^nx^k\binom{n}{k} \]

两边同时求导：

\[n(1+x)^{n-1}=\sum_{k=0}^nkx^{k-1}\binom{n}{k} \]

两边同乘 \(x\)：

\[nx(1+x)^{n-1}=\sum_{k=0}^nkx^k\binom{n}{k} \]

两边同时求导：

\[n((1+x)^{n-1}+(n-1)x(1+x)^{n-2})=\sum_{k=0}^nk^2x^{k-1}\binom{n}{k} \]

将 \(x=1\) 带入得到：

\[\sum_{k=0}^nk^2\binom{n}{k}=n(n+1)2^{n-2} \]

组合数取模

卢卡斯定理：

\[\binom{n}{m}=\binom{n\bmod p}{m\bmod p}\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\pmod p \]

例题

\(n\) 个不同元素，选 \(r\) 个，每个可以选择多次（类似多重背包）。求方案数。

这个问题等价于 \(n\) 个未知数和为 \(r\) 的方案数。引用上面的结论即可。

\(n\) 个不同元素，选 \(r\) 个，选的元素不能相邻。

考虑空格的分配。
\(r\) 个元素，显然有 \(r+1\) 个空格（算上两边），其中，两头的两个的空格最少可以是 \(0\) 个格子，中间的空格最少是 \(1\) 个格子。
因为要选 \(r\) 个物品，所以有 \(n-r\) 个格子是空格。
问题转化为 \(r+1\) 个未知数，和为 \(n-r\)，其中 \(r-1\) 个下界为 \(1\)，剩下的两个下界为 \(0\)。
套用上面的公式，答案即为 \(\binom{n-r-(r-1)+(r+1)-1}{(r+1)-1}=\binom{n-r+1}{r}\)。

求 \(\sum_{k=0}^n\binom{n}{k}^2\)。

考虑 \(\binom{n}{k}=\binom{n}{n-k}\)，那么上式变为 \(\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}\)。
就相当于把 \(2n\) 个物品分成两段，枚举前面半段选多少，后面半段选多少。
显然等于 \(\binom{2n}{n}\)。

将 \(x\) 拆分为 \(n\) 个不同的组合数之和，求一组合法方案。

\(x=\sum_{i=1}^{k-1}\binom{i}{0}+\binom{x-k+1}{1}\)。

比较 \(\binom{n_1}{m_1}\) 和 \(\binom{n_2}{m_2}\) 的大小，\(n,m\le 10^6\)。

预处理阶乘的 \(\log\)，比较 \(\log\) 的大小。

错排

设 \(D_n\) 表示 \(n\) 个元素错排的方案数。

如果 \(n=0\)，只能啥也不干，所以 \(D_0=1\)。

如果 \(n=1\)，没法错排，所以 \(D_1=0\)。

如果 \(n=2\)，只能交换两个元素，所以 \(D_2=1\)。

考虑加入第 \(n\) 个元素，假设放在了第 \(i\) 个位置。显然有 \((n-1)\) 个 \(i\) 可选。

对于每个 \(i\)，考虑第 \(i\) 号元素放在哪。

放在 \(n\) 号位置。这样剩下的 \((n-2)\) 个元素错排即可。
不放在 \(n\) 号位置。因为 \(i\) 不能放在 \(n\)，而且因为原先的 \(i\) 位置被占用，就相当于没有，那么 \(n\) 号位置就相当于 \(i\) 号位置。这样 \((n-1)\) 个元素错排即可。

综上，\(D_n=(n-1)(D_{n-1}+D_{n-2})\)。

斯特林数

第二类

\(\begin{Bmatrix}n\\m\end{Bmatrix}\) 表示把 \(n\) 个元素划分成 \(m\) 个不可区分的非空集合的方案数。

转移

\(0\) 个东西放在 \(0\) 个集合里面只能啥也不干，所以 \(\begin{Bmatrix}0\\0\end{Bmatrix}=1\)。

考虑加入一个元素。

如果这个元素放在一个独立的集合内，有一种方案，剩下的部分有 \(\begin{Bmatrix}n-1\\m-1\end{Bmatrix}\) 种。

如果放在一个已有的集合内，有 \(k\) 种方案，剩下的部分有 \(\begin{Bmatrix}n-1\\m-1\end{Bmatrix}\) 种方案。

所以：

\[\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1 \\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix} \]

第一类

\(\begin{bmatrix}n\\m\end{bmatrix}\) 表示把 \(n\) 个元素划分成 \(m\) 个不可区分的非空轮换的方案数。

一个轮换就是一个首尾相接的环形排列。

我们可以写出一个轮换 \([A,B,C,D]\)，并且我们认为 \([A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]\)，即，两个可以通过旋转而互相得到的轮换是等价的。

注意，我们不认为两个可以通过翻转而相互得到的轮换等价，即 \([A,B,C,D]\neq[D,C,B,A]\)。

转移

\(0\) 个东西放在 \(0\) 个轮换里面只能啥也不干，所以 \(\begin{bmatrix}0\\0\end{bmatrix}=1\)。

考虑加入一个元素。

如果这个元素放在一个独立的轮换内，有一种方案，剩下的部分有 \(\begin{bmatrix}n-1\\m-1\end{bmatrix}\) 种。

如果放在一个已有的集合内，有 \((n-1)\) 种方案，剩下的部分有 \(\begin{bmatrix}n-1\\m-1\end{bmatrix}\) 种方案。

所以：

\[\begin{bmatrix}n\\k\end{bmatrix}=\begin{bmatrix}n-1 \\k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix} \]

通常幂和下降幂的转换

下降幂转通常幂:

\[x^{\underline{n}}=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}x^k \]

通常幂转下降幂：

\[x^n=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}} \]

容斥

通过集合交的大小，求出集合并的大小。

设 \(U\) 中元素有 \(n\) 种不同的属性，而第 \(i\) 种属性称为 \(P_i\)，拥有属性 \(P_i\) 的元素构成集合 \(S_i\)，那么：

\[\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right| \]

错排

这里有 \(n\) 个条件，形如 \(i\) 在正确的位置上。

显然，错排方案数=全排列-有至少一个在正确的位置上的的方案数。

考虑如何求出有至少一个在正确的位置上的方案数。

考虑容斥。满足任意 \(k\) 个条件的方案数是：\(\binom{n}{k}\times (n-k)!=\frac{n!}{k!}\)，容斥系数为 \(k-1\)。

综上，错排方案数为：

\[\begin{align} D(n)&=n!-\sum_{k=1}^n(-1)^{k-1}\frac{n!}{k!}\nonumber\\ &=n!+\sum_{k=1}^n(-1)^k\frac{n!}{k!}\nonumber\\ &=\sum_{k=0}^n(-1)^k\frac{n!}{k!}\nonumber\\ \end{align} \]

但是这个式子就算预处理逆元都是 \(\Theta(n)\) 的，而且 \(\Theta(n)\) 的时间只能求一项，没啥用。