计数原理
计数技巧
等效替代（映射）：
构造一个映射，将每一种原问题的方案映射为新问题的一种方案，并使答案更容易计算。
例如捆绑法，插空法，隔板法等。
捆绑法：也成整体法，即若要求若干物品相邻，可以将他们视作一个整体来计数。
插空法：如果要求若干物品两两不相邻，可以先将其他物品放好，然后将这些物品插入空挡当中进行计数。
隔板法：将不可区分物品分配问题、不定方程整数解问题转化为插板组合问题。
经典例题：把 $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!} $$
性质
$C^m_n=C^{n-m}_n$
$C^m_n=C^m_{n-1}+C^{m-1}_{n-1}$
$C^0_n+C^1_n+C^2_n+ \dots +C^n_n=2^n$
证明
由组合数的定义, 对于从 $n$ 个不同元素中取出 $m$ 个组成的每个集合, 剩余末取 出的元素也构成一个集合, 两个集合一一对应, 所以性质 1 成立。
从 $n$ 个不同元素中取出 $m$ 个组成一个集合有两类方法: 取 $n$ 号元素、不取 $n$ 号元素。若取 $n$ 号元素, 则应在剩余 $n-1$ 个元素中选出 $m-1$ 个, 有 $C_{n-1}^{m-1}$ 种取法。若不取 $n$ 号元素, 则应在剩余 $n-1$ 个元素中选出 $m$ 个, 有 $C_{n-1}^m$ 种取法。根 据加法原理, 性质 2 成立。
从 $n$ 个不同元素中取出若干个元素组成一个集合, 有 $n+1$ 类方法, 分别是取出 $0,1,2, \cdots, n$ 个。根据加法原理, 共有 $C_n^0+C_n^1+C_n^2+\cdots+C_n^n$ 种方法。从另一个方面去想, $n$ 个元素每个元素可以取或不取, 总方法数为 $2^n$, 二者相等, 故性质 3 成立。 证毕。
$\frac{k}{n}C_{n}^{k}=C_{n-1}^{k-1}$;
证明
$C^k_n = \frac{n!}{(n-k)!}$，乘上 $\frac{k}{n}$ 就变成 $\frac{(n-1)!}{(k-1)!(n-k)!}$ 即 $C^{k-1}_{n-1}$。
$C^1_{n+1} + C^2_{n+2} + C^3_{n+3} + \dots C^k_{n+k} = C^{k}_{n+k+1} - 1$
证明
由定理 $1$ 可知，
原式 = $C^n_{n+1} + C^n_{n+2} + C^n_{n+3} + \dots C^n_{n+k}$.
我们往原式补一个 $C^{n+1}_{n+1}$，为保证式子结果不变，再减去一个 $1$，即，
原式 = $C^{n+1}_{n+1} + C^n_{n+1} + C^n_{n+2} + C^n_{n+3} + \dots C^n_{n+k}-1$.
此时第一项和第二项可以用定理 $2$ 合并，
原式 = $C^{n+1}_{n+2} + C^n_{n+2} + C^n_{n+3} + \dots C^n_{n+k}-1$.
以此类推，原式最终可以变成 $C^{n+1}_{n+k+1} - 1$ 即 $C^k_{n+k+1} - 1$.
求组合数
递推求组合数
杨辉三角，$C^m_n=C^m_{n-1}+C^{m-1}_{n-1}$。
时间复杂度 $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，...
经典问题
模型之间可以互相转化。
- 在 $n \times n$ 的网格中，一开始在 $(0,0)$ 处，每次可以向上走一格或者向右走一格，在任一时刻，向右走的次数不能少于向上走的次数，求合法路径的数量。
- 给定 $n$ 个 0 和 $n$ 个 1 ，它们将按照某种顺序排成长度为 $2n$ 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。
- 求 $n$ 个左括号和 $n$ 个右括号构成的合法括号序列的数量。
- 将 $1, 2, 3, \dots , n - 1, n$ 依次加入栈，求合法出栈序列的数量。
例题：https://www.luogu.com.cn/problem/P1044。
- 求 $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)*f(0)$。
其中 $f(0)=f(1)=1$。
即 $f(n)=\sum^{n}_{i=1}f(i-1)*f(n-i)$。
这与卡特兰数的递推公式一致。
