计数原理

计数技巧

等效替代（映射）：

构造一个映射，将每一种原问题的方案映射为新问题的一种方案，并使答案更容易计算。
例如捆绑法，插空法，隔板法等。

捆绑法： 也成整体法，即若要求若干物品相邻，可以将他们视作一个整体来计数。

插空法： 如果要求若干物品两两不相邻，可以先将其他物品放好，然后将这些物品插入空挡当中进行计数。

隔板法： 将不可区分物品分配问题、不定方程整数解问题转化为插板组合问题。

经典例题： 把 $n$ 个相同的苹果分给 $k$ 个人，要求每人至少分到一个的方案数。（求解不定方程 $x_1+x_2+...+x_k=n$（$\forall i \in [1, k], 1 \le x_i \le n$） 的解的个数）。
解决方案： 有 $n-1$ 个空隙，在这些空隙中插入 $k-1$ 个板将苹果分为 $k$ 部分，方案数为 $C^{k-1}_{n-1}$。

拓展问题 1： 求解不定方程 $x_1+x_2+...+x_k=n$（$\forall i \in [1, k], 0 \le x_i \le n$） 的解的个数。
解决方案： 将每个 $x$ 提前加一个 $1$，问题变成了 “求解不定方程 $x_1+x_2+...+x_k=n+k$（$\forall i \in [1, k], 1 \le x_i \le n+k$） 的解的个数。”。

拓展问题 2： 求解不定方程 $x_1+x_2+...+x_k \le n$（$\forall i \in [1, k], 1 \le x_i \le n$） 的解的个数。
解决方案： 添加一个新的板子放在最后面。问题变成了将 $n$ 分成 $k+1$ 部分，前 $k$ 份元素个数大于等于 $1$ 的方案数。

容斥原理

摩根定理

交集的补等于补集的并，并集的补等于补集的交。

$\overline{A \cap B} = \overline{A} \cup \overline{B}，\overline{A \cup B} = \overline{A} \cap \overline{B}$。

---

$|A \cup B| = |A| + |B| - |A \cap B|$

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

另一种形式：

$$\left | \bigcup_{i=1}^nA_i \right | = \sum_{Subset \ \subseteq \ \{1, 2, \dots n\} \ \not= \ \emptyset}(-1)^{\left |Subset \right| + 1} \times \left | \bigcap_{j \ \subseteq \ Subset} A_j\right |$$

排列组合

排列数

将 $n$ 个不同的物品排成一行，有多少种不同的顺序？

$$1 \times 2 \times 3 \times \dots \times n = n!$$

从 $n$ 个不同物品中选出 $k$ 个，考虑每个数的顺序，有多少种不同的选法，写作 $A^k_n$。

排列数计算公式：

$$(n-k+1) \times (n-k+2) \times (n-k+3) \times \dots \times n = \frac{n!}{(n-k)!}$$

组合数

从 $n$ 个不同的物品中选出 $k$ 个，不考虑每个数的顺序，有多少种不同的选法，写作 $C^k_n$ 或 $\binom{n}{k}$。

$$\binom{n}{k} = C^k_n = \frac{n!}{k!(n-k)!}$$

$$\binom{n}{k} = \frac{n \times (n-1) \times \dots \times (n-k+1)}{k!}$$

性质

$\binom{n}{m}=\binom{n}{n-m}$

$\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$

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

证明
由二项式定理 $2^n=(1+1)^n=\sum_{i=0}^n\binom{n}{i}$。

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

证明
$\binom{n}{k} = \frac{n!}{(n-k)!k!}$，乘上 $\frac{k}{n}$ 就变成 $\frac{(n-1)!}{(k-1)!(n-k)!}$ 即 $\binom{n-1}{k-1}$。

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

证明
由定理 $1$ 可知，
原式 = $\sum_{i=1}^k\binom{n+i}{n}$.
我们往原式补一个 $\binom{n+1}{n+1}$，再减去一个 $1$，即，
原式 = $\binom{n+1}{n+1} + \sum_{i=1}^k\binom{n+i}{n}-1$。

此时第一项和第二项可以用定理 $2$ 合并，
原式 = $\binom{n+1}{n+2} + \sum_{i=2}^k\binom{n+i}{n}-1$.
以此类推，原式最终可以变成 $\binom{n+k+1}{n+1} - 1$。

$\sum_{j=i}^n\binom{j-1}{i-1}=\binom{n}{i}$

$\binom{n}{m}$ 为奇数当且仅当 $n \ \& \ m=m$ ，$\&$ 为按位与，此为 Lucas 定理的推论。

错排问题

有 $n$ 个编号为 $1\sim n$ 的盒子，另有 $n$ 个编号为 $1\sim n$ 的球，求每个球都放入与其编号不同的盒子的方案数 $D_n$。

方法 1：容斥原理

$$D_n=\sum_{i=0}^n (-1)^i\binom{n}{i}(n-i)!$$

化简得：

$$D_n=n!\sum_{i=0}^n \frac{(-1)^i}{i!}$$

容易得到递推公式为：

$$D_n=nD_{n-1}+(-1)^n$$

方法 2：计数原理

考虑编号为 $n$ 的球，它可以放入其他 $n-1$ 个盒子中得一个，因此有 $n-1$ 种方案。

考虑编号为 $n$ 的球放在编号为 $k$ 的盒子中，那么若编号 $k$ 的球放在第 $n$ 个盒子中，则剩下 $n-2$ 对球和盒子形成一个新的错排问题，方案数为 $f(n-2)$，若编号为 $k$ 的球不放在第 $n$ 个盒子中，那么剩下 $n-1$ 个球和 $n-1$ 个盒子由于这个新限制形成一个新的错排问题，方案数为 $f(n-1)$。

根据计数原理原理，有 $D_n=(n-1)(D_{n-1}+D_{n-2})$。

运用一个巧妙的代数变形（参考书上的推导）：

$$\begin{align*} D_{n}-n D_{n-1} & = (n-1)\left(D_{n-1}+D_{n-2}\right)-n D_{n-1} \\ & = -\left[D_{n-1}-(n-1) D_{n-2}\right] \\ & = (-1)^{2}\left[D_{n-2}-(n-2) D_{n-3}\right] \\ & = \cdots \\ & = (-1)^{n-2}\left(D_{2}-2 D_{1}\right) \\ & = (-1)^{n} \\ \Rightarrow D_{n} & = n D_{n-1}+(-1)^{n} \end{align*}$$

染色问题

问题 1： 给出一条长度为 $n$ 的链，有 $m$ 种颜色，要求相邻两个位置颜色不同，求染色的方案数 $A_{n,m}$。

根据乘法原理易得 $A_{n,m}=m(m-1)^{n-1}$。

问题 2： 给出一条长度为 $n$ 的圆环，有 $m$ 种颜色，要求相邻两个位置颜色不同，求染色的方案数 $A_{n,m}$。

若没有 $n$ 与 $1$ 颜色不同的限制，则问题等价于长度为 $n$ 的链，因此我们考虑对 $n$ 位置讨论：

• 若 $n$ 位置与 $1$ 位置颜色相同，则将 $n$ 位置与 $1$ 位置合并成一块，则新问题变成了求 $A_{n-1,m}$。
• 若 $n$ 位置与 $1$ 位置颜色不同，则与原问题等价，及 $A_{n,m}$。

所以有 $A_{n-1,m}+A_{n,m}=m(m-1)^{n-1}$。

对等式变形：

$$A_{n,m}=-A_{n-1,m}+m(m-1)^{n-1}$$

设 $p\in \R$，令其满足：

$$A_{n,m}+p(m-1)^n=-[A_{n-1,m}+p(m-1)^{n-1}]$$

则有 $-p-p(m-1)=m$，解得 $p=-1$，即 $A_{n,m}-(m-1)^n=-[A_{n-1,m}-(m-1)^{n-1}]$。

所以有 $\{A_{n,m}-(m-1)^n\}$ 为公比为 $-1$ 的等比数列，且 $A_{1,m}=m,A_{2,m}=m(m-1)$，因此有

$$\begin{align*} A_{n,m}-(m-1)^n&=(-1)^{n-2}[A_{2,m}-(m-1)]\\ &=(-1)^n[A_{2,m}-(m-1)^2] \\ &=(-1)^n[m(m-1)-(m-1)^2] \\ &=(-1)^n(m-1) \\ \Rightarrow A_{n,m} &=(-1)^n(m-1)+(m-1)^n \end{align*}$$

圆排列

求 $n$ 个不同元素形成的长度为 $n$ 的轮换数。

轮换指的是一个元素集合的环形排列（循环排列），例如 $[A, B, C]$、$[B, C, A]$、$[C, A, B]$ 都是同一个轮换。

方法一： 容易发现一个轮换对应 $n$ 个不同的排列，所以圆排列数 $a_n=\frac{n!}{n}=(n-1)!$。

方法二： 我们可以固定其中一个元素（如第一个元素），则然后对剩下的 $n-1$ 个元素进行线性排列，所以圆排列数 $a_n=(n-1)!$。

事实上这个问题是第一类斯特林数的特殊情况 $[{n \atop 1}]$（见后文第一类斯特林数）。

求组合数

递推求组合数

杨辉三角，$\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$

时间复杂度 $O(nm)$。

预处理求组合数

原理：递推求阶乘逆元，见数论笔记。

预处理：

fact[0] = 1;
for (int i = 1; i < mod; i ++ ) fact[i] = 1ll * fact[i - 1] * i % mod;
inv[mod - 1] = qpow(fact[mod - 1], mod - 2);
for (int i = mod - 2; i >= 0; i -- ) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;

查询：

int C(int a, int b) {
	if (b > a) return 0;
	return 1ll * fact[a] * inv[a - b] % mod * inv[b] % mod;
}

int P(int a, int b) {
	if (b > a) return 0;
	return 1ll * fact[a] * inv[a - b] % mod;
}

时间复杂度：预处理 $O(n + \log p)$，查询 $O(1)$；

Lucas 定理

$C_{m}^{n} \equiv C_{m \bmod p}^{n \bmod p}\cdot C_{\lfloor m/p \rfloor}^{\lfloor n/p \rfloor} \pmod p$。

int lucas(int n, int m) {
	if (!m) return 1;
	return C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod;
}

时间复杂度：

• 查询 $O(n \log n)$；
• 预处理组合数，预处理 $O(n + \log p)$，查询 $O(\log n)$。

分解质因数求组合数

void get_primes(int n) {
	for (int i = 2; i <= n; i ++ ) {
		if (!notp[i]) primes[ ++ pcnt] = i;
		for (int j = 1; primes[j] <= n / i && j <= pcnt; j ++ ) {
			notp[primes[j] * i] = true;
			if (i % primes[j] == 0) break;
		}
	}
}

int fact(int n, int p) {
	int res = 0;
	while (n) res += n / p, n /= p;
	return res;
}

int C(int n, int m) {
	int ans = 1;
	for (int i = 1; i <= pcnt; i ++ ) {
		cnt[pri[i]] = fact(2 * n, pri[i]) - fact(n, pri[i]) - fact(n + 1, pri[i]);
		for (int j = 1; j <= cnt[pri[i]]; j ++ ) ans = (ll)ans * pri[i] % p;
	}
	return ans;
}

int main() {
	get_primes(N);
	return 0;
}

时间复杂度：$O(\frac{n}{\ln n} \log n)$

高精度求组合数

在 分解质因数求组合数 的基础上写一个高精度乘法即可。

string mul(string a, int b) {
	string c;
	int t = 0;
	for (int i = 0; i < a.size() || t; i ++ ) {
		if (i < a.size()) t += (a[i] - '0') * b;
		c += t % 10 + '0';
		t /= 10;
	}
	return c;
}

string C(int n, int m) {
	for (int i = 1; i <= pcnt; i ++ ) cnt[primes[i]] = getc(n, primes[i]) - getc(m, primes[i]) - getc(n - m, primes[i]);
	string res = "1";
	for (int i = 1; i <= pcnt; i ++ ) {
		for (int j = 1; j <= cnt[primes[i]]; j ++ ) {
			res = mul(res, primes[i]);
		}
	}
	reverse(res.begin(), res.end());
	return res;
}

时间复杂度：$O(\frac{n}{\ln n} \times len_{max} \log n)$

组合数前缀和

令 $f_{n,k}=\sum_{i=0}^k\binom{n}{i}$。

问题：给出 $k$，求 $f_{n,k}$

令 $g_i=f_{i,k}$，那么 $g_0=0$，$g_i=2\times g_{i-1}-\binom{i-1}{k}$，$g_i$ 即为所求。

证明

$$\begin{align*} g_n=\sum_{i=0}^k\binom{n}{i}=\\ \sum_{i=0}^k\binom{n-1}{i}+\sum_{i=1}^k\binom{n-1}{i-1}=\\ 2\times\sum_{i=0}^k\binom{n-1}{i}-\binom{n-1}{i}=\\ 2\times g_{n-1}-\binom{n-1}{i} \end{align*}$$

博客：https://www.cnblogs.com/wenmoor/p/18236009

多重集排列数与多重集组合数

多重集排列数 | 多重组合数

多重集是指包含重复元素的广义集合。设 $S=\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}$ 表示由 $n_1$ 个 $a_1, n_2$ 个 $a_2 ， \ldots, n_k$ 个 $a_k$ 组成的多重集，则 $S$ 的全排列个数为

$$\frac{N!}{\prod_{i=1}^k n_{i} !}=\frac{N!}{n_{1} ! n_{2} ! \cdots n_{k} !}$$

多重集的排列数又称多重组合数。

多重集组合数

问题 1： 设 $S=\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}$ 表示由 $n_1$ 个 $a_1, n_2$ 个 $a_2 ， \ldots, n_k$ 个 $a_k$ 组成的多重集，则从 $S$ 中取出 $r \ (\forall i \in [1, k], r \leq n_i)$ 个元素的方案数为

$$C_{r+k-1}^{k-1}$$

证明
$x_1+x_2+\cdots+x_k=r$ 且 $x_i \geq 0$ (隔板法)
答案为 $C_{r+k-1}^{k-1}$。

问题 2： 设 $S=\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}$ 表示由 $n_1$ 个 $a_1, n_2$ 个 $a_2 ， \ldots, n_k$ 个 $a_k$ 组成的多重集，则从 $S$ 中取出 $r \ (r \leq \sum_{i=1}^{k} n_i)$ 个元素的方案数为

$$C_{k+r-1}^{k-1}-\sum_{i=1}^{k}C_{k+r-n_{i}-2}^{k-1}+\sum_{1\leq i\lt j\leq k}C_{k+r-n_{i}-n_{j}-3}^{k-1}-\cdots+(-1)^{k}C_{k+r-\sum_{i=1}^{k-1}n_{i}-(k+1)}^{k-1}$$

证明
首先考虑每个元素有无限个的情况，相当于从多重集 $S=\left\{\infty \cdot a_1, \infty \cdot a_2, \cdots, \infty \cdot a_k\right\}$ 中选出 $r$ 个元素，根据 问题 1，方案数为 $C_{k+r-1}^{k-1}$。
考虑减法原理，设 $S_i(1 \leq i \leq k)$ 表示至少包含 $n_i+1$ 个 $a_i$ 的多重集。我们先从 $S$ 中取出 $n_i+1$ 个 $a_i$, 然后再任选 $r-n_i-1$ 个元素, 即可构成 $S_i$ 。与上面同理, 可以构成的 不同 $S_i$ 的数量为 $C_{k+r-n_i-2}^{k-1}$。
进一步地，先从 $S$ 中取出 $n_i+1$ 个 $a_i$ 和 $n_j+1$ 个 $a_j$，然后再任选 $r-n_i-n_j-2$ 个元素，即可构成 $S_i \cap S_j$, 方法数为：

$$C_{k+r-n_i-n_j-3}^{k-1}$$

根据容斥原理, 至少有一种 $a_i$ 选取的数量超过 $n_i$ 限制的多重集共有：

$$\left|\bigcup_{i=1}^k s_i\right|=\sum_{i=1}^k C_{k+r-n_i-2}^{k-1}-\sum_{1 \leq i<j \leq k} C_{k+r-n_i-n_j-3}^{k-1}+\cdots+(-1)^{k+1} C_{k+r-\sum_{i=1}^k n_i-(k+1)}^{k-1}$$

故满足所有限制的合法多重集共有 $C_{k+r-1}^{k-1}-\left|\cup_{i=1}^k S_i\right|$ 个。

卡特兰数（Catalan-Number）

卡特兰数（Catalan Number）是组合数学中一个常出现在各种计数问题中的数列。

• 数列的前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862，...

计算公式

通项公式：

$$\frac{\binom{2n}{n}}{n+1}=\frac{(2n)!}{(n+1)!n!}$$

递推式：

$$f(n)=\sum^{n}_{i=1}f(i-1)\times f(n-i)$$

经典问题

模型之间可以互相转化。

1. 在 $n \times n$ 的网格中，一开始在 $(0,0)$ 处，每次可以向上走一格或者向右走一格，在任一时刻，向右走的次数不能少于向上走的次数，求合法路径的数量。

2. 给定 $n$ 个 0 和 $n$ 个 1 ，它们将按照某种顺序排成长度为 $2n$ 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。

3. 求 $n$ 个左括号和 $n$ 个右括号构成的合法括号序列的数量。

4. 将 $1, 2, 3, \dots , n - 1, n$ 依次加入栈，求合法出栈序列的数量。

例题：https://www.luogu.com.cn/problem/P1044。

5. 求 $n$ 个节点构成的不同的二叉树的数量。

证明 1
在满二叉树上向下走 $n$ 次再向上走 $n$ 次，回到根节点，保证任意时刻向下走的次数大于等于向上走的次数。
这样就转化成了问 问题 2。

证明 2
设 $f(n)$ 为 $n$ 个节点构成的二叉树的数量，那么 $f(n)=f(0) \times f(n-1)+f(1) \times (n-2) + \dots + f(n-1)\times f(0)$。
其中 $f(0)=f(1)=1$。
即 $f(n)=\sum^{n}_{i=1}f(i-1)\times f(n-i)$。
这与卡特兰数的递推公式一致。

扩展 - 高维卡特兰数

TYOJ N0611 填数2

通过 DP/打表 $n=3$ 可以发现此时 $f(m)=2\times\frac{(3m)!}{m!(m+1)!(m+2)!}$。
$n=4$ 可以发现此时 $f(m)=12\times\frac{(4m)!}{m!(m+1)!(m+2)!(m+3)!}$。

容易发现前面的系数就是 $\prod_{i=1}^{n-1}i!$。

总结可以得到 $f(n,m)=\prod_{i=1}^{n-1}i!\times\frac{(nm)!}{\prod_{i=0}^{n-1}(m+i)!}$。

斯特林数

第一类斯特林数

第一类斯特林数（斯特林轮换数）$[{n \atop k}]$ ，也可记做 $s(n, k)$ ，表示将 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空轮换的方案数。

词语	含义
轮换	指的是一个元素集合的环形排列（循环排列），例如 $[A, B, C]$、$[B, C, A]$、$[C, A, B]$ 都是同一个轮换。
互不区分	不考虑轮换之间的顺序，也就是说，把元素分成若干个轮换后，不关心这些轮换的排列顺序。

圆桌问题： 有 $n$ 个人要坐在 $k$ 张圆桌上，每张桌子至少坐一个人，桌子之间不区分顺序，桌上座位是环形排列，求方案数。答案显然是第一类斯特林数 $[{n \atop k}]$。

递推公式

$$\left[{n\atop k}\right]=\left[{n-1 \atop k-1}\right]+(n-1)\left[{n-1 \atop k}\right]$$

该递推式的证明可以考虑其组合意义。

我们插入一个新元素时，有两种方案：

• 将该新元素置于一个单独的轮换中，共有 $\left[{n-1 \atop k-1}\right]$ 种方案；
• 将该元素插入到任何一个现有的轮换中，对于这 $k$ 个轮换中的任意一个轮换，将该元素插在任意一个元素后面均是不同的轮换，因此这 $k$ 个轮换共有 $n-1$ 个可插入位置，共有 $(n-1)\left[{n-1 \atop k}\right]$ 种方案。

根据加法原理，将两式相加即可得到递推式。

第二类斯特林数

第二类斯特林数（斯特林子集数）$\left\{ {n \atop k} \right\}$，也可记做 $S(n, k)$，表示将 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空子集的方案数。

递推公式

$$\left\{ {n\atop k} \right\}=\left\{ {n-1\atop k-1} \right\}+k\left\{ {n-1\atop k} \right\}$$

边界是 $\left\{ {n\atop 0} \right\}=[n=0]$。

该递推式的证明可以考虑其组合意义。

我们插入一个新元素时，有两种方案：

• 将新元素单独放入一个子集，有 $\left\{ {n-1\atop k-1} \right\}$ 种方案；
• 将新元素放入一个现有的非空子集，有 $k\left\{ {n-1\atop k} \right\}$ 种方案。

根据加法原理，将两式相加即可得到递推式。