0x0 基本原理

0x01 加法原理

若做 $A$ 有 $n$ 种方法，做 $B$ 有 $m$ 种方法，并且它们互不干涉，那么做 $A$ 或 $B$ 中的恰好一个有 $n+m$ 种方法。

0x02 乘法原理

若做 $A$ 有 $n$ 种方法，做 $B$ 有 $m$ 种方法，并且它们互不干涉，那么做 $A$ 并且做 $B$ 有 $n\times m$ 种方法。

0x1 排列组合

0x11 排列

从 $n$ 个各不相同的元素中有顺序地取出 $m$ 个元素的方法数，记为 $A_n^m$ ，即为排列数。

考虑 $A_n^m$ 的具体求法。考虑每一次选出的元素，第一次选择有 $n$ 种方法，第二次选择有 $n-1$ 种方法， $\dots$ ，第 $m$ 次选择有 $n-m+1$ 种方法。由于每次选择事件互不干涉，所以根据乘法原理：

A_n^m=n(n-1)(n-2)\dots(n-m+1)=\dfrac{n!}{(n-m)!}

0x12 组合

从 $n$ 个各不相同的元素中无顺序地取出 $m$ 个元素的方法数，记为 $C_n^m$ 或 $\dbinom{n}{m}$ ，即为组合数。

考虑 $C_n^m$ 的具体求法。无顺序地取出可以看作是有顺序地取出后去掉顺序，那么由于 $m$ 个各不相同的元素有 $m!$ 种排列方式，所以：

C_n^m=\dfrac{A_n^m}{m!}=\dfrac{n!}{(n-m)!m!}

0x13 排列数与组合数的求法

在实际应用中，排列数和组合数都可以通过预处理阶乘的方法来求出。

但是组合数有 $O(nm)$ 的预处理方法（ $n$ 是元素个数上限， $m$ 是选出的元素数量上限）：

C^m_n=C^{m-1}_{n-1}+C^{n-1}_m

证明：

首先把 $n$ 个物品分成两组，第一组有 $n-1$ 个，第二组有 $1$ 个。

那么我们可以从第一组里选 $m-1$ 个并从第二组里选一个，或者从第一组里选 $m$ 个。

预处理组合数的代码：（对 $p$ 取模）

C[0][0]=1;
for(int i=1;i<=n;i++)
{
	C[i][0]=1;
	for(int j=1;j<=i;j++)
	{
		C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
	}
}

另外，关于组合数的取模问题，可以看组合数取模（Lucas 定理 & exLucas 定理）学习笔记。

0x14 一些技巧

0x141 整体考虑

有时候元素会分成很多个组，组之间有顺序关系，组内也有顺序关系，那么就可以考虑每一组单独排列组合，再把每一组当成单个元素来排列组合。

0x142 插板法

$n$ 个相同的物品放到 $m$ 个不同的盒子内，不允许空盒子，有多少种方法？

可以考虑在 $n$ 个物品中间放 $m-1$ 个“隔板”，把所有物品分隔成 $m$ 组，那么方案数就是 $C_{n-1}^{m-1}$ 。

插板法还有个变形，即允许空盒子：

$n$ 个相同的物品放到 $m$ 个不同的盒子内，不允许空盒子，有多少种方法？

可以考虑增加 $m$ 个物品，那么盒子里放一个物品就相当于是没有放，放两个就相当于是放了一个，依此类推。所以方案数即为 $C_{n+m-1}^{m-1}$ 。

0x143 贡献有次方的处理

权值为 $x$ 的方案贡献为 $x^k$ 的时候，可以考虑运用二项式定理拆开次方，也可以考虑组合意义： $n$ 个对象， $k$ 个人各选一个的方案数。

例题：P1758 [NOI2009] 管道取珠 | 题解

0x144 组合恒等式

详见组合恒等式学习笔记。

0x145 格路计数

详见格路计数入门。

1x0 二项式定理

(a+b)^n=\sum\limits_{i=0}^n\dbinom{n}{i}a^ib^{n-i}

证明：

首先考虑把 $(a+b)^n$ 的幂拆开：

(a+b)^n=\begin{matrix}\underbrace{(a+b)(a+b)(a+b)\dots(a+b)}\\n\text{个}(a+b)\end{matrix}

接下来拆括号，考虑选 $i$ 个 $a$ 出来，那么就会有 $n-i$ 个 $b$ 和它配对，即 $a^ib^{n-i}$ ，选 $a$ 出来的方案数是 $\dbinom{n}{i}$ ，所以原式成立。

1x1 容斥原理

1x11 基础容斥

设有一些元素和一些条件 $R=\{P_1,P_2,P_3,\dots\}$ ，令 $f(S)$ 表示满足 $S$ 中所有条件的元素个数。那么至少满足 $R$ 中一个条件的元素个数为：

\sum\limits_{T\subseteq R,T\not=\varnothing}(-1)^{|T|-1}f(T)

可以靠维恩图来理解：

至少满足一个条件的元素个数可以看作是维恩图中不是空白的部分的面积，是

|A|+|B|+|A|-|AC|-|AB|-|BC|+|ABC|

仔细观察就会发现它与式子一致。

不满足 $R$ 中任意一个条件的元素个数为：

\sum\limits_{T\subseteq R}(-1)^{|T|}f(T)

依旧是靠之前那一张维恩图来理解，不满足任意一个条件的元素个数可以看作维恩图中空白部分的面积，是

\text{元素个数}-|A|-|B|-|C|+|AC|+|AB|+|BC|-|ABC|

而元素个数就是 $f(\varnothing)$ ，这也是求和里的 $T$ 可以等于 $\varnothing$ 的原因。

1x12 基础容斥扩展

依旧是有一些元素和一些条件 $R=\{P_1,P_2,P_3,\dots\}$ ， $f(S)$ 依旧表示满足 $S$ 中所有条件的元素个数。令 $g(S)$ 表示满足且仅满足 $S$ 中所有条件的元素个数，那么有：

g(S)=\sum\limits_{S\subseteq T}(-1)^{|T|-|S|}f(T)

还是靠维恩图理解：

满足且仅满足某个集合中的条件的元素个数可以看成是一块颜色的面积。假设要求 $g(A)$ 也就是维恩图中黄色那块的面积。那么显然它是

|A|-|AC|-|AB|+|ABC|

仔细观察就会发现它与式子一致。

1x13 容斥底层原理

其实所有容斥都可以这样描述：

假设现在要计数集合 $S$ 中满足条件（ $01$ 函数） $P(x)$ 的元素 $x$ 的个数，即 $|\{x|x\in S,P(x)=1\}|$ 。

容斥其实使用一系列简单的条件 $Q_i(x)$ 和容斥系数 $f_i$ 去表示 $P(x)$ 。具体的，我们会计算 $\sum_i|\{x|x\in S,Q_i(x)=1\}|\times f_i$ 使得 $x$ 恰好被计算 $P(x)$ 次，即 $\sum_iQ_i(x)f_i=P(x)$ 。

举个例子，Loj #3395. 「2020-2021 集训队作业」Yet Another Permutation Problem 这题，需要计算不存在长度为 $k$ 连续上升段的排列个数。那么对于一个排列 $x$ ，不难发现它一定可以分成若干段极长上升段，不妨设这些上升段长度为 $a_1,a_2,\dots,a_m$ ，则显然 $P(x)=\prod [a_i< k]$ ，不妨设 $R(x)=[x< k]$ ，则 $P(x)=\prod R(a_i)$ 。

考虑极长不好算，不妨算钦定，即每次钦定往后接一段上升段。不难发现这样是好转移的，有 $ans_i=\sum\limits_{j=0}^{i-1}ans_j\times \binom{i}{j}\times f_{i-j}$ ，其中 $f_l$ 是往后钦定接一段长 $l$ 的上升段的容斥系数。

考虑如何计算 $f_l$ ，只需满足长 $x$ 的极长段被计算到的次数 $g_x=R(x)=[x<k]$ 次。

设 $f$ 的 OGF 为 $F(x)=\sum\limits_{i=1}^{\infin} f_ix^i$ ，则有 $g_i=[x^i]\sum\limits_{i=1}^\infin F^{i}(x)=[x^i]\left(\frac{1}{1-F(x)}-1\right)$ 。

求逆即可，或者可以观察系数规律。

2x0 各种常见数列

2x01 卡特兰数

有 $n$ 个左括号和 $n$ 个右括号的合法括号序列有多少个？

把左括号记为 $1$ ，右括号记为 $-1$ ，不难发现一个括号序列合法当且仅当其前缀和均 $\ge0$ 。

直接计算不好做，考虑寻找映射关系。对于每个不合法的括号序列，考虑把其前缀和中第一个 $<0$ 的位置和其之前的括号都翻转。由于翻转之前这个位置的前缀和一定为 $-1$ ，所以翻转后的序列共有 $n+1$ 个 $1$ 和 $n-1$ 个 $-1$ 。

不难发现，每个有 $n+1$ 个 $1$ 和 $n-1$ 个 $-1$ 的序列都对应一个不合法序列，只要把其前缀和中第一个 $>0$ 的位置和其之前的括号都翻转即可还原出一个不合法序列，并且是一一对应的，所以不合法的括号序列总共有 $\binom{2n}{n-1}$ 个。

由于总共的括号序列有 $\binom{2n}{n}$ ，所以合法括号序列有 $\binom{2n}{n}-\binom{2n}{n-1}=\frac{(2n)!}{n!^2}-\frac{(2n)!}{(n-1)!(n+1)!}=\frac{(2n)!(n+1)-n(2n)!}{n!^2(n+1)}=\frac{\binom{2n}{n}}{n+1}$ 。

这就是卡特兰数的通项公式，不妨记 $C_n=\frac{\binom{2n}{n}}{n+1}$ ，那么有 $C_{n+1}=\sum\limits_{i=0}^{n}C_iC_{n-i}$ 。

证明：

假设最后一个右括号和第 $i+1$ 个左括号匹配，那么这对括号中间和这对括号外面的部分是互相独立的，所以此时的合法括号序列个数为 $C_iC_{n-i}$ 。

一些运用：

有 $n$ 个点的有根二叉树的个数？

设 $f_n$ 表示问题的答案，那么有 $f_n=\sum\limits_{i=0}^{n-1}f_{i}f_{n-1-i}$ 且 $f_0=f_1=1$ ，和卡特兰数的递推式一致，所以有 $f_n=C_n$ 。
有 $n$ 个点的所有有根二叉树的叶子的总数？

对于每棵 $n$ 个点的二叉树，设它有 $k$ 个叶子，那么把这 $k$ 个叶子分别删去就能得到 $k$ 棵 $n-1$ 个点的二叉树。

由于每一颗 $n-1$ 个点的二叉树都能悬挂 $n$ 个新的叶子，所以每一棵 $n-1$ 个点的二叉树都会被上面的过程得到 $n$ 次。

由于 $n$ 个点的有根二叉树有 $C_n$ 种，所以 $n$ 个点的所有二叉树总共有 $nC_{n-1}=\binom{2n-2}{n-1}$ 个叶子。

组合计数入门