排列组合
一，概念
排列：指从给定个数的元素中取出指定个数的元素进行排序；
组合：从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。
排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切。
二，原理
1. 加法原理
设集合 \(S\) 被划分为两两不相交的若干部分 \(S_1,S_2,...,S_n\)，则 \(S\) 的对象数目可以通过确定它的每一部分对象数目并如此相加得到，符号化表示为 \(|S|=|S_1|+|S_2|+...+|S_n|\)。
例子
设学校田径运动会中，学生要从田赛或径赛中选一个项目。若选田赛，则有三种选择。若选径赛，则有两种选择。
使用加法原理，共有 \(3+2=5\) 种报名方案。
2. 乘法原理
令 \(S\) 是对象的有序对 \((a,b)\) 的集合，其中第一个对象 \(a\) 来自大小为 \(p\) 的一个集合，而对于对象 \(a\) 的每一个选择，对象 \(b\) 有 \(q\) 种选择，于是集合 \(S\) 的大小为 \(p\times q\)，符号化表示为 \(|S|=p\times q\)
例子
设在面馆要点一碗面，面的粗细有三种，而配料有两种，任选一种粗细并搭配任意一种配料。
使用乘法原理，共有 \(3\times 2=6\) 种配搭。
事实上，乘法原理是加法原理的一个推论，根据对象 \(a\) 的不同选择 \(a_1,a_2,...,a_p\) 将 \(S\) 划分为不相交的集合 \(S_1,S_2,...,S_p\)，由于 \(b\) 的选择不受 \(a\) 的选择的影响，故每个 \(S_i\) 的大小都是 \(q\)，于是根据加法原理，我们可以得到 \(|S|=\) \(|S_1|+|S_2|+...+|S_n|=\) \(q+q+...+q=p\times q\)。
三，计算
1. 排列数
从 \(n\) 个不同的元素中，任取 \(m\) 个元素按照一定的顺序排成一列，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的一个排列，所有此类排列的总数叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的排列数，用符号 \(A_n^m\) 表示。
排列数的计算公式如下：
\(A_n^m=\) \(n(n-1)(n-2)...(n-m+1)=\) \(\frac{n!}{(n-m)!}\)
特别地，当 \(m\) 等于 \(n\) 时，这类排列被称为全排列，全排列的排列数 \(A_n^n=n!\)。
2. 组合数
从 \(n\) 个不同的元素中，任取 \(m\) 个元素组成一个集合，叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的一个组合，所有此类组合的总数叫做从 \(n\) 个不同元素中取出 \(m\) 个元素的组合数，用 \(\binom{n}{m}\) 表示，读作“\(n\) 选 \(m\)”。
组合数的计算公式如下：
\(\binom{n}{m}=\) \(\frac{A_n^m}{m!}=\) \(\frac{n!}{m!(n-m)!}\)
组合数也可以表示为 \(C_n^m\)，但 \(\binom{n}{m}\) 被较为普遍地采用。
四，性质
简单组合数性质
\(\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\)
\(\binom{n}{m}=\binom{n}{n-m}\)
\(\binom{n+r+1}{r}=\sum_{i=0}^r\binom{n+i}{i}\)
\(\binom{n}{m}\binom{m}{r}=\binom{n}{r}\binom{n-r}{m-r}\)
\(m\binom{n}{m}=n\binom{n-1}{m-1}\)
\(\binom{n+m}{r}=\sum_{i=0}^r\binom{n}{i}\binom{m}{r-i}\)
\(\sum_{i=0}^n i\binom{n}{i}=n2^{n-1}\)
五，技巧
插板法
插板法是用于求一类给相同元素分组方案数的技巧，也可用于求一类先行不定方程的解的组数。以下是插板法的几个经典应用场景
正整数和的数目
现有 \(n\) 个完全相同的元素，要求将其分为 \(k\) 组，保证每组至少有一个元素，一共有多少种分法。
考虑拿 \(k-1\) 块板子插入到 \(n\) 个元素两两形成的 \(n-1\) 个空隙里，可以将 \(n\) 个元素分为 \(k\) 组。
因为元素是完全相同的，所以答案是 \(\binom{n-1}{k-1}\)。
本质是求 \(x_1+x_2+...+x_k=n\) 的方案数。
非负整数和的数目
此时若直接插板，可能会出现多块板子插到一个空里的情况，这时我们可以创造 \(k\) 个虚拟元素依次填入每一组，转化为上问的问题，于是答案为 \(\binom{n+k-1}{k-1}\)，也就是 \(\binom{n+k-1}{n}\)。
不同下界整数和的数目
本质是求 \(x_1+x_2+...+x_k=n\) 的方案数，并要求 \(x_i\geq a_i\)。
类比无限制情况，创造 \(\sum a_i\) 个虚拟元素保证第 \(i\) 组分到 \(a_i\) 个，之后插板即可。
答案为 \(\binom{n-\sum a_i+k-1}{n-\sum a_i}\)
六，斯特林数
1. 第一类斯特林数
又称斯特林轮换数，表示将 \(n\) 个元素划分为 \(k\) 个圆排列的方案数。
排成 \(k\) 个圆排列可以理解成求 \(1~n\) 排列的个数中满足 \(i\) 向 \(p_i\) 连一条边后，形成 \(k\) 个环的图的个数。
对这样的图计数可以推出 \(n\brack m\) 的递推式，考虑加入点 \(n\)，第一种情况是 \(n\) 形成了一个新的环，方案数 \(n-1\brack m-1\)；另一种情况是插入已有的环中，由于每个点有唯一后继，所以可以插入任一点及其后缀之间，方案数为 \((n-1){n-1\brack m}\)。
综上，我们可以得到 \({n\brack m}={n-1\brack m-1}+(n-1){n-1\brack m}\)。
2. 第二类斯特林数
又称斯特林子集数，表示将 \(n\) 个元素划分为 \(k\) 个集合的方案数。
依旧考虑递推 \(n\brace m\)，考虑加入最后一个元素的方案数。第一种情况是单独加入一个新集合，对应方案数为 \(n-1\brace m-1\)；否则选择一个新的集合加入，对应方案数为 \(m{n-1\brace m}\)。
综上，我们可以得到 \({n\brace m}={n-1\brace m-1}+m{n-1\brace m}\)。
在实际应用中，第二类斯特林数更为常见。
七，卡特兰数
引入
考虑如下问题：
\(n\) 个数 \(1,2,...,n\) 依次进栈，问有多少种不同的出栈序列。
求长为 \(2n\) 的合法括号序列的数量。
求 \(2n+1\) 个点，每个非叶子节点都恰有两个儿子的有根无号区分左右儿子二叉树的数量。
给定 \((n+1)\times (n+1)\) 的网格图，问有多少种从 \((1,1)\) 出发到 \((n+1,n+1)\) 的不越过对角线的路径数量。
这四个问题其实是等价的。
对于 2，左括号看作入栈，右括号看作出栈，转化为问题 1；对于 3，考虑树的 dfs 序，左儿子看作左括号，右儿子看作右括号，则 dfs 序与长为 \(2n\) 的合法括号序列对应；对于 4，向右走看作入栈，向上走看作出栈，等价于 1。
这些问题的答案被称为卡特兰数，记作 \(C_n\)。
推导
我们可以由第四个问题推出卡特兰数的表达式。首先，如果没有不能越过对角线这一性质，方案数显然是 \(\binom{2n}{n}\)，在越过对角线的方案中路径一定解除了次对角线 \(y=x+1\)，将路径第一次与次对角线接触位置之后的部分关于这条次对角线对称，路径终点变成了 \((n-1,n+2)\)，发现这样操作后不合法方案与 \((1,1)\) 到 \((n-1,n+2)\) 的路径一一对应，所以最终 \(C_n=\) \(\binom{2n}{n}-\binom{2n}{n-1}=\) \(\frac{\binom{2n}{n}}{n+1}\)。
递推式
\(C_n\) 满足递推式 \(C_n=\sum_{i\geq 0}C_iC_{n-1-i}\)。
证明
考虑括号序列，左括号视为 +1，右括号视为 -1，合法括号序列等价于前缀和恒费负且序列和为 0 的序列。
枚举第一个前缀和为 \(0\) 的位置，并以此将括号序列分为两部分，前一部分是长为 \(2(i-1)\) 的合法括号序列，后一部分是长为 \(2*(n-i)\) 的合法括号序列，于是可以得到 \(C_n\) 满足递推式 \(C_n=\sum_{i\geq 0}C_iC_{n-1-i}\)。
八，容斥
1. 容斥原理
若 \(A_1,A_2,...,A_n\) 为有限集，则 \(|\bigcup_{i=1}^n A_i|=\) \(\sum_{1\leq i\leq n}A_i-\) \(\sum_{1\leq i\leq j\leq n}|A_i\cap A_j|+...+\) \((-1)^{n-1}|A_1\cap ...\cap A_n|\)。
2. 子集容斥
\(g(S)=\sum_{T\subset S}f(T)\)，\(f(S)=\sum_{T\subset S}(-1)^{|S|-|T|}g(T)\)。
证明：
\(\sum_{T\subset S}(-1)^{|S|-|T|}g(T)\)
\(=\sum_{T\subset S}(-1)^{|S|-|T|}\sum_{R\subset T}f(R)\)
\(=\sum_{R\subset S}f(R)\sum_{R\subset T\subset S}(-1)^{|S|-|T|}\)
当 \(R=S\) 时，\(\sum_{R\subset T\subset S}(-1)^{|S|-|T|}=1\) 否则 \(\forall a\in S-R\)，\(f:T\leftrightarrow T\oplus {a}\) 为双射，故 \(\sum_{R\subset T\subset S}(-1)^{|S|-|T|}=0\)
于是 \(f(S)=\sum_{T\subset S}(-1)^{|S|-|T|}g(T)\)。
九，二项式
1. 二项式定理
\(n\in ℕ,(x+y)^n=\sum_{k=0}^n\binom{n}{k}x^ky^{n-k}\)
此外还有广义二项式定义：\(|x|<1,\alpha\in ℝ\)，则 \((x+1)^{\alpha}=\sum_{k=0}^{\infty}\binom{\alpha}{k}x^k\)，此处的 \(\binom{\alpha}{k}:=\frac{a^{\underline{k}}}{k!}\)。\(|x|\geq 1\) 时，右侧幂级数不一定收敛。
2. 二项式反演
\(g_i=\) \(\sum_{k\geq i}\binom{k}{i}f_k\)，\(f_i=\) \(\sum{k\geq i}\binom{k}{i}(-1)^{k-i}g_k\)
证明：
\(\sum_{k\geq i}\binom{k}{i}(-1)^{k-i}g_k\)
\(=\sum_{k\geq i}\binom{k}{i}(-1)^{k-i}\sum_{j\geq k}\binom{j}{k}f_j\)
\(=\sum_{j\geq i}f_j\sum_{i\leq k\leq j}\binom{k}{i}\binom{j}{k}(-1)^{k-i}\)
\(=\sum_{j\geq i}f_j\frac{j!}{i!}\sum_{i\leq k\leq j}\frac{1}{(j-k)!(k-i)!}(-1)^{k-i}\)
\(=\sum_{k\geq i}\sum_{j\geq k}f_j\frac{j!(-1)^{k-i}}{i!(j-k)!(k-i)!}\)
\(=\sum_{k\geq i}\sum_{j\geq
k}f_j\binom{j}{k}\binom{k}{i}(-1)^{k-i}\)
\(=\sum_{k\geq i}\sum_{j\geq k}f_j\binom{j}{i}\binom{j-i}{k-i}1^{j-k}(-1)^{k-i}\)
\(=\sum_{j\geq i}f_j\binom{j}{i}(1-1)^{j-i}\)
\(=\sum_{j\geq i}f_j\binom{j}{i}0^{j-i}\)
仅当 \(j=i\) 时，\(f_j\binom{j}{i}0^{j-i}\) 有值，值为 \(f_i\)，故 \(f_i=\) \(\sum{k\geq i}\binom{k}{i}(-1)^{k-i}g_k\)。
类似地：
\(g_i=\) \(\sum_{k\leq i}\binom{i}{k}f_k\)，\(f_i=\) \(\sum{k\leq i}\binom{i}{k}(-1)^{i-k}g_k\)
3. 二项式反演应用
共有 \(n\) 个位置，需要令恰好 \(k\) 个位置满足某个限制，我们可以钦定 \(k\) 个位置满足该性质，未钦定部分算出所有可能方案，利用二项式反演算出恰好 \(k\) 个的方案数。
例子：求长为 n 的错排个数
钦定 \(k\) 个位置不是错排，\(f_k\) 表示恰好 \(k\) 个位置不是错排的数量，\(g_k\) 表示 \(k\) 个位置是错排，其余部分任意的排列数量，于是我们要求的是 \(f_0\)，根据二项式反演，\(f_0=\) \(\sum_{k\geq 0}\binom{k}{0}(-1)^{k-0}g_k=\) \(\sum_{k\geq 0}(-1)^kg_k\)。
易得 \(g_k=\binom{n}{k}(n-k)!\)，即从 \(n\) 个位置中选 \(k\) 个使强制满足条件，余下部分求全排列数量。
故 \(f_0=\) \(\sum_{k\geq 0}(-1)^k\binom{n}{k}(n-k)!\)。