计数原理

计数技巧

等效替代（映射）：

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

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

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

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

经典例题： 把 $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}=\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)$。

exLucas 定理

分解质因数求组合数

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 jcfact(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]] = jcfact(2 * n, pri[i]) - jcfact(n, pri[i]) - jcfact(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)$

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

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

多重集是指包含重复元素的广义集合。设 $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)!}$。