计数原理
计数技巧
等效替代（映射）：
构造一个映射，将每一种原问题的方案映射为新问题的一种方案，并使答案更容易计算。
例如捆绑法，插空法，隔板法等。
捆绑法： 也成整体法，即若要求若干物品相邻，可以将他们视作一个整体来计数。
插空法： 如果要求若干物品两两不相邻，可以先将其他物品放好，然后将这些物品插入空挡当中进行计数。
隔板法： 将不可区分物品分配问题、不定方程整数解问题转化为插板组合问题。
经典例题： 把 $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}$
错排问题
有 $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*} $$
求组合数
递推求组合数
杨辉三角，$\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) $$
经典问题
模型之间可以互相转化。
- 在 $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)\times f(0)$。
其中 $f(0)=f(1)=1$。
即 $f(n)=\sum^{n}_{i=1}f(i-1)\times f(n-i)$。
这与卡特兰数的递推公式一致。
扩展 - 高维卡特兰数
通过 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)!}$。
