梦回选修 \(2\) QAQ。这东西说实话的确考察思维，而且容易和 dp 什么的综合起来难度就直接飙到 \(*3000\)，但是组合数学的确是一个极其重要的部分，它可以在很多情况下帮你减少枚举次数（比如去年 T2 的哈希做法如果最后直接组合数学统计答案的话码量少了整整 \(30\) 行！），所以这也是以后的重点。
组合数学还是要写一些概念的。
加法/乘法原理
忘了就真可以 AFO 了。
排列数
\[A_n^m = \frac{n!}{(n - m)!} \]圆排列
\[Q_n^m = \frac{A_n^m}{m} \]组合数
\[C_n^m= \begin{pmatrix} n\\m\end{pmatrix} = \frac{A_n^m}{m!} = \frac{n!}{m!(n - m)!} \]通常写成圆括号形式，读作“\(n\) 选 \(m\)”。
特别地，当 \(m > n\) 时排列数和组合数都为 \(0\)。
组合数有一些优美的定理：
基本性质 \(1\)
\[\begin{pmatrix} n\\m\end{pmatrix} = \begin{pmatrix} n - 1\\m\end{pmatrix} + \begin{pmatrix} n - 1\\m - 1\end{pmatrix} \]基本性质 \(2\)
\[\begin{pmatrix} n\\m\end{pmatrix} = \begin{pmatrix} n\\n - m\end{pmatrix} \]吸收恒等式（提取公约数）：
\[\begin{pmatrix} n\\m\end{pmatrix} = \frac{n}{m}\begin{pmatrix} n - 1\\m - 1\end{pmatrix} \]上指标求和：
\[\sum_{i = m} ^ n \begin{pmatrix} i\\m\end{pmatrix} = \begin{pmatrix} n + 1\\m + 1\end{pmatrix} \]两边同时加上为 \(0\) 的 \(\begin{pmatrix} m\\m + 1\end{pmatrix}\) 可以得证。
平行恒等式：
\[\sum _ {i = 0} ^ n \begin{pmatrix} m + i\\i\end{pmatrix} = \begin{pmatrix} m + n + 1\\n\end{pmatrix} \]范德蒙德卷积：
\[\sum _{i = 0}^k \begin{pmatrix} n\\i\end{pmatrix}\begin{pmatrix} m\\k - i\end{pmatrix} = \begin{pmatrix} n + m\\k\end{pmatrix} \]相当于枚举前 \(n\) 个数选了多少个。
推论1：
\[\sum _ {i = -r} ^ s \begin{pmatrix} n\\r + i\end{pmatrix}\begin{pmatrix} m\\s - i\end{pmatrix} = \begin{pmatrix} n + m\\r + s\end{pmatrix} \]推论2：
\[\sum_{i = 1} ^ n \begin{pmatrix} n\\i\end{pmatrix}\begin{pmatrix} n\\i - 1\end{pmatrix} = \begin{pmatrix} 2n\\n - 1\end{pmatrix} \]推论3：
\[\sum_{i = 0} ^ n \begin{pmatrix} n\\i\end{pmatrix}^2 = \begin{pmatrix} 2n\\n\end{pmatrix} \]推论4：
\[\sum _ {i = 0} ^ m \begin{pmatrix} n\\i\end{pmatrix}\begin{pmatrix} m\\i\end{pmatrix} = \begin{pmatrix} n + m\\m\end{pmatrix} \]这是一个网格图路径计数的典型证明。
二项式定理
梦回选修 \(2\) 第二弹 QAQ。
\[(a + b) ^ n = \sum _{i = 0} ^ n \begin{pmatrix} n\\i\end{pmatrix} a^{n -i}b^{i} \]整式乘法可证。
特殊情况：
\[\sum_{i = 0} ^ n \begin{pmatrix} n\\i\end{pmatrix} = 2 ^ n \]当 \(a = b = 1\) 可得。
\[\sum_{i = 0} ^ n (-1)^n \begin{pmatrix} n\\i\end{pmatrix} = [n = 0] \]当 \(a = 1,b = -1\) 时可得。
Lucas 定理
\[\begin{pmatrix} n\\m\end{pmatrix} \mod p = (\begin{pmatrix} n \mod p\\m \mod p\end{pmatrix}\begin{pmatrix} \lfloor \frac{n}{p} \rfloor \\\lfloor \frac{m}{p} \rfloor\end{pmatrix})\mod p \]插板法
Q1：\(n\) 个相同元素分成非空的 \(m\) 组。
考虑将 \(m - 1\) 个板子插入 \(n - 1\) 个空中，所以答案为 \(\begin{pmatrix} n - 1\\m - 1\end{pmatrix}\)。
Q2：\(n\) 个相同元素分成可空的 \(m\) 组。
考虑转化为 Q1，于是只要“借” \(m\) 个元素插进来即可，答案为 \(\begin{pmatrix} n + m - 1\\m - 1\end{pmatrix} = \begin{pmatrix} n + m - 1\\n\end{pmatrix}\)。
实质上是求 \(\sum_{i = 1}^k x_i = n\) 的非负整数解的组数。
小球与盒子
路径计数
Q1：从 \((0,0)\) 走到 \((n,m)\) 的路径方案数：
比较 naive。
\[\begin{pmatrix} n + m\\m\end{pmatrix} \]Q2：从 \((0,0)\) 走到 \((n,n)\) 除端点外不接触直线 \(y = x\) 的非降路径数：
先考虑 \(y = x\)下方的路径，都是从 \((0,0)\) 出发，经过 \((1, 0)\) 及 \((n, n - 1)\) 到 \((n,n)\)，可以看做是 \((1,0)\) 到 \((n, n- 1)\) 不接触 \(y = x\) 的非降路径数。
所有的的非降路径有 \(\begin{pmatrix} 2n - 1\\n - 1\end{pmatrix}\) 条。对于这里面任意一条接触了 \(y = x\) 的路径，可以把它最后离开这条线的点到 \((1, 0)\) 之间的部分关于 \(y = x\) 对称变换，就得到从 \((0, 1)\) 到 \((n, n - 1)\) 的一条非降路径。反之也成立。从而 \(y = x\) 下方的非降路径数是 \(\begin{pmatrix} 2n - 1\\n - 1\end{pmatrix} - \begin{pmatrix} 2n - 1\\n - 1\end{pmatrix}\)。根据对称性可知所求答案为 \(2\begin{pmatrix} 2n - 1\\n - 1\end{pmatrix} - 2\begin{pmatrix} 2n - 1\\n - 1\end{pmatrix}\)。
Q3：从 \((0,0)\) 走到 \((n, n)\) 除端点外不穿过直线 \(y = x\) 的非降路径数：
用类比 Q2 的方法可以得到：
例题
P3197 HNOI2008 越狱
简单高中数学。直接算不够方便，于是考虑容斥。总方案数为 \(n ^ m\)，相邻宗教不同方案数为 \(m·(m - 1)^{n - 1}\)（第一个人能选 \(m\) 种宗教而其他人只能选剩下的不与前一个人重合的 \(m - 1\) 种），相减即可。
这个题目启发我们要学会用容斥等方法转换问题，从而使繁题简化。
P5520 yLOI2019 青原樱
因为 \(m\) 个樱花树幼苗之间必隔 \(m - 1\) 个空，我们考虑填上这些空，总空位变为 \(n - m + 1\)。接下来我们就是在 \(n - m + 1\) 个空中选 \(m\) 个空插，由于是有序的方案，所以答案为 \(A_{n - m + 1} ^ m\)。
标签：begin,end,组合,sum,frac,pmatrix,数学,2n From： https://www.cnblogs.com/endswitch/p/18375726