蓝月の笔记——排列组合篇
摘要
万恶的数学！
Part 1 加乘原理
小学奥数内容
加法原理：当多个方案并列（即互不影响）时，总方案数为各个方案数之和
例：共有 \(k\) 种交通工具可以从A地到B地，第 \(i\) 种交通工具有 \(a_i\) 班次，那么从A地到B地的总方案数为 \(\sum_{1 \le i \le k} a_i\)
乘法原理：当多个方案分步完成时，总方案数为各步方案数之积
例：从 \(1\) 地到 \(k\) 地，规定只能从 \(i\) 地单项移动到 \(i+1\) 地，且有 \(a_i\) 种路线，那么从 \(1\) 地到 \(k\) 地的总方案数为 \(\prod_{i \le i < k}a_i\)
Part 2 排列组合数
排列数
从 \(n\) 个小朋友种选择 \(k\) 个小朋友排成一队的方法数，记为 \(\mathrm{A}_n^k\)
公式推导
选第 \(1\) 个小朋友有 \(n\) 种方案，选第 \(2\) 个小朋友有 \(n-1\) 种方案（因为有一个被选了），\(\cdots\)，选第 \(k\) 个小朋友有 \(n-k+1\) 种方案
根据乘法原理，\(\mathrm{A}_n^k=\prod_{(n-k+1) \le i \le n} i=\large\frac{n!}{(n-k)!}\)
组合数
从 \(n\) 个小朋友种选择 \(k\) 个小朋友的方法数（不考虑顺序），记为 \(\mathrm{C}_n^k\)
公式推导
选出 \(k\) 个不考虑顺序的小朋友，相当于选出 \(k\) 个考虑顺序的小朋友再打乱顺序，除以顺序数即可
\(\mathrm{C}_n^k = \large\frac{\mathrm{A}_n^k}{k!}=\large\frac{n!}{(n-k)!k!}\)
对称性
在 \(n\) 个里面选 \(k\) 个相当于在 \(n\) 个里面选 \(n-k\) 个丢掉，所以 \(\mathrm{C}_{n}^{k}=\mathrm{C}_{n}^{n-k}\)
多重组合数
实际上是全排列，有 \(k\) 对多胞胎，共 \(n\) 个人，第 \(i\) 对有 \(a_i\) 个人，因为每一对多胞胎之间长得太像了，所以在给他们排队时会把他们是为同一个人（即交换位置只算做一种方案），排队的方案数即为多重组合数，记为 \(\large{n \choose {a_1,a_2,\cdots,a_k}}\)
公式推导
假设多胞胎交换位置算作多种方案，答案显然为 \(n!\)
每一对多胞胎之间都有 \(a_i!\) 种先后位置关系，将这些重复计算除掉即可，\(\large{n \choose {a_1,a_2,\cdots,a_k}}=\large\frac{n!}{\prod_{1 \le i \le k}a_i!}\)
Part 3 插板法
可以理解为求不定方程 \(\sum_{1 \le i \le k} x_i=n\) 的解的数量
\(x_i > 0\)
在 \(n\) 个 \(1\) 之间的 \(n-1\) 空插 \(k-1\) 个板子，分成的 \(k\) 个空间的 \(1\) 的个数为每一个 \(x_i\) 的值
答案为 \(\mathrm{C}_{n-1}^{k-1}\)
\(x_i \ge 0\)
在 \(n\) 个 \(1\) 后补 \(k\) 个 \(1\)，再插 \(k-1\) 个板子，最后拿掉补的 \(k\) 个 \(1\)，就可以留出 \(0\) 个 \(1\) 的区间了
答案为 \(\mathrm{C}_{n+k-1}^{k-1}=\mathrm{C}_{n+k-1}^{n}\)（对称性）
\(x_i \ge a_i\)
令 \(t=\sum a_i,s_i=x_i-a_i\)
在 \(n\) 个 \(1\) 后补 \(t\) 个 \(1\)，此时可以保证 \(k\) 个区间内都达到了 \(x_i \ge a_i\) 的要求，那么原方程转化为 \(\sum_{1 \le i \le k} (s_i+a_i)=n\)，则 \(\sum_{1 \le i \le k} s_i=n-t(s_i \ge 0)\)，变成了 \(x_i \ge 0\) 的形式，按公式求解即可
答案为 \(\mathrm{C}_{n-t+k-1}^{n-t}\)
Part 4 杨辉三角&二项式定理
杨辉三角：
\[1 \]\[1\,\,1 \]\[1\,\,2\,\,1 \]\[1\,\,3\,\,3\,\,1 \]\[1\,\,4\,\,6\,\,4\,\,1 \]\[\cdots\cdots\cdots\cdots \]通过瞪眼法可以知道，杨辉三角的第 \(i\) 行 \(j\) 个数为 \(\mathrm{C}_{i-1}^{j-1}\)
再次通过瞪眼法可以知道，杨辉三角最左一列和最右一列都是 \(1\)，其它数都是它左上的数和右上的数的和，那么组合数的递推式就是 \(\mathrm{C}_{i}^{j}=\mathrm{C}_{i-1}^{j}+\mathrm{C}_{i-1}^{j-1}\)
再再次通过瞪眼法，可以发现杨辉三角的第 \(i\) 列为 \((x+y)^{i-1}\) 展开后每一项的系数，这就是二项式定理，用公式表示为：
\[(x+y)^n=\sum_{0 \le i \le n}\mathrm{C}_{n}^{i}x^iy^{n-i} \]将二项式推广为多项式，同理可得 \((\sum_{1 \le i \le k}x_i)^n=\sum_{(a_1,a_2,\cdots,a_k)满足性质P}({n \choose {a_1,a_2,\cdots,a_k}}\prod_{1 \le i \le k}x_i^{a_i})\)
我们称 \(k\) 元组 \((a_1,a_2,\cdots,a_k)\) 满足性质 \(P\)，当且仅当 \(\forall i \in [1,k],x_i=a_i\) 是不定方程 \(\sum_{1 \le i \le k}x_i=n\) 的一组解
Part 5 圆排&项链排&错排
圆排列
\(n\) 个人坐在一个圆桌上吃饭，排位置的方案数就是圆排列数（旋转前后算一种方案）
显然为全排列除以旋转次数，\(R_{n}=\frac{\mathrm{A}_n^n}{n}=(n-1)!\)
项链排列
\(n\) 个不同的珠子串成一个项链，可以串成的项链数量就是项链排列数（旋转、翻转前后算一种方案）
在圆排列的基础上除以两种翻转方式，\(N_n=\frac{R_n}{2}=\frac{(n-1)!}{2}\)
错位排列（信封问题）
例题终于有题了
令 \(p\) 是 \(1 \sim n\) 的一个排列，如果 \(\forall i \in [1,n],p_i \not= i\)，那么我们称 \(p\) 是 \(n\) 的一个错位排列
错排数可以使用递推求解，Oi Wiki上已经讲的很清楚了，我就（懒）不（得）讲了
Code:
d[0] = 1, d[1] = 0, d[2] = 1;
for (int i = 3; i < kMaxN; i++) {
d[i] = ((i - 1) * ((d[i - 1] + d[i - 2]) % kP)) % kP;
}