写了有点久，基本都写得oiwiki上的但自认为写的更好(至少对于我自己的理解来说)
定义基础
排列
从\(n\)个元素中考虑顺序地选出\(k\)个元素的方案数，写作\(A_n^k\)。
显然：
\[A_n^k = \frac{n!}{(n - k)!} \]
圆上排列
一个长度为\(n\)的圆环上选一段长度为\(k\)的段的排列数，写作\(Q_n^k\)。
当 $ n = k\(，显然有 ：\)Q_n^n = \frac{A_n^n}{n}$
推广到 ，于是有：\(Q_n^k = \frac{A_n^k}{k}\)
组合
从\(n\)个元素中不计顺序地选出\(k\)个元素的方案数，写作\(C_n^k\)或\(\binom{n}{k}\)。
有：
\[\binom{n}{k} = \frac{n!}{(n - k)!k!} \]
杨辉三角
$ \binom{i}{j} $ 的值实际上等于杨辉三角的第\(i\)行\(j\)列。（若不存在则等于\(0\)）
插板法
技巧的实现
现有\(n\)个 完全相同 的元素，要求将其分为\(k\)组，保证每组至少有一个元素，一共有多少种分法？
考虑拿\(k - 1\)块板子插入到\(n\)个元素两两形成的\(n - 1\)个空里面，答案：
\[\binom{n - 1}{k - 1} \]
本质
求解 $x_1 + x_2 + x_3 + \cdots + x_k = n $的正整数解的组数。
变式
允许空集：
等于再加了\(k\)个空能拿来插以作为空集。
\[\binom{n + k - 1}{k - 1} = \binom{n + k - 1}{n} \]
*显然对于组合数，有:\(\binom{n}{m} = \binom{n}{n - m}\)
其本质可以扩展到求解 $x_1 + x_2 + x_3 + \cdots + x_k = n $的非负整数解的组数。
对于每个\(x_i\)都有各自的下界，即求 $x_1 + x_2 + x_3 + \cdots + x_k = n $ 且\(x_i \ge a_i\)：
显然可以将\(n\)减去\(\sum a_i\)，即每个\(x_i\)都先取一个\(a_i\)。
然后对于剩下的就转换成了允许空集的情况，显然有答案：
\[\binom{n + k - \sum a_i - 1}{n - \sum a_i} \]
不相邻排列
从\(1\)~\(n\)中取\(k\)个数不存在两个相邻的数字的方案数。
可以理解为于\(n\)中刨去\(k - 1\)个数，再选\(k\)个数。刨去的\(k - 1\)个数使得这\(k\)个数中每两个数间的其中一个数能被刨去，这样不论怎么选都是合法的。
\[\binom{n - (k - 1)}{k} = \binom{n - k + 1}{k} \]
进阶结论
多重集排列数 （多重组合数）
这两个名字表示的一个东西，都是一个多重集（不是集合，内部有序且有重复数字）的排列个数。
对于一个多重集\(S = {n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k}\)，内含\(n_i\)个\(a_i\)，其排列个数为：
\[\binom{n}{n_1, n_2, \cdots, n_k} = \frac{n!}{n_1! n_2! \cdots n_k!} = \frac{n!}{\Pi_{i = 1}^{k} n_i!} \]
先算出所有元素的排列数，再一次除以每种元素内部的排列数。
多重集的组合数
等价于求解 $x_1 + x_2 + x_3 + \cdots + x_k = n\(的非负整数解的组数 (\)\binom{n + k - 1}{n}$)
二项式定理
\[(a + b) ^ n = \sum_{i = 0}^{n} \binom{n}{i} a ^ i b ^ {n - i} \]
证明：数学归纳法
能证明到：
\[\binom{n}{k} + \binom{n}{k - 1} = \binom{n + 1}{k} \]
扩展至多项式：
\[(x_1 + x_2 + \cdots + x_t) ^ n = \sum_{x_1 + x_2 + x_3 + \cdots + x_k = n 的非负整数解} \binom{n}{n_1, n_2, \cdots, n_k} x_1^{n_1}x_2^{n_2}... \]
当\(x_1 = x_2 = \cdots = x_t\)，
\[\sum \binom{n}{n_1, n_2, \cdots, n_k} = t ^ n \]
各种推论
1.
对于定义，显然：
\[\binom{n}{k} = \frac{n}{k} \binom{n - 1}{k - 1} \]
可以将组合数拆乘多项式进行证明
2.
对于从\(n\)中取\(m\)个，对于第\(m\)个数取不取分类，根据定义显然有：
\[\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1} \]
3.
我们假设要从\(n\)个数中选若干个数(也可能不选)。
对于枚举选多少个来算答案，显然有:
\[\sum_{i = 0}^{n} \binom{n}{i} \]
对于枚举每一为选不选，显然有：
\[2 ^ n \]
于是我们得到了：
\[\sum_{i = 0}^{n} \binom{n}{i} = 2 ^ n \]
不难发现这个是二项式定理在两项皆为的常数\(1\)时的结论。
4.
考虑另一种二项式定理的特殊情况，两项分别为\(1\)&\(-1\)，\(n = 0\)，显然有：$ \sum_{i=0}^{n} (-1)^{i} \binom{n}{i} = [n = 0]$
5.\(\mathit{Vandermonde} 卷积\)
也叫范德蒙德恒等式。
\[\binom{n + m}{k} = \sum_{i = 0}^{k} \binom{n}{i}\binom{m}{k - i} \]
证明：
对于一个集合大小为\(n\)要选\(k\)个元素，可以将其拆成两个大小分别为\(n\)与\(m\)的集合，分别枚举两个集合各选多少。
6.
当范德蒙德卷积中，\(n = m = k\)时，显然有：
\[\binom{2n}{n} = \sum_{i = 0}^n\binom{n}{i}\binom{n}{n - i} \]
即：
\[\binom{2n}{n} = \sum_{i = 0}^n\binom{n}{i}^2 \]
7.
\[\sum_{i = 0} ^ n i \binom{n}{i} = n2^{n - 1} \]
证明：
观察到等式的右边与3式右边的等式的求导形式一样，考虑对3式等式左边也进行求导。
考虑对二项式定理左边求导，并带入\(b = 1\)：
\[(\sum_{i = 0}^ n \binom{n}{i} a^i) ^\prime = \sum_{i = 0}^n \binom{n}{i}ia^{i - 1} \]
再将\(a = 1\)带入：
\[(\sum_{i = 0}^ n \binom{n}{i} a^i) ^\prime = \sum_{i = 0}^n \binom{n}{i}ia^{i - 1} = \sum_{i = 0}^n i \binom{n}{i} \]
得证。
8.
\[\sum_{i=0}^{n} i^2 \binom{n}{i} = n{(n+1)}{2^{n-2}} \]
类比7式，再导一次(?)。
9.朱世杰恒等式
\[\sum_{l=0}^{n} \binom{l}{k} = \binom{n+1}{k+1} \]
这其实是组合数在使用杨辉三角进行求值的形式。（可以画个图看一下）
10.
若\(F_x\)表示斐波那契数列第\(x\)项，则有：
\[\sum_{i=0}^{n} \binom{n-i}{i} = F_{n+1} \]
考虑数学归纳法。
当\(k = 0, 1\)时，\(F_0 = 1, F_1 = 1\)，显然成立。
当\(k > 1\)，假设等式成立。
\[\therefore F_{k - 1} = \sum_{i = 0}^{k - 1} \binom{k - i - 1}{i} \\ F_{k} = \sum_{i = 0}^{k} \binom{k - i}{i}\\ F_{k + 1} = \sum_{i = 0}^{k + 1} \binom{k - i + 1}{i} \]
\[\therefore F_{k + 1} = \sum_{i = 0}^{k + 1} \binom{k - i + 1}{i}\\ = 1 + \sum_{i = 1}^{k + 1} \binom{k + 1 - i}{i}\\ = 1+ \sum_{i = 1}^{k + 1} \binom{k - i}{i - 1} + \sum_{i = 1}^{k + 1} \binom{k + 1 - i}{i - 1}\\ \]
\[\therefore F_{k + 1} = 1 + \sum_{i = 0}^{k} \binom{k - i}{i} + \sum_{i = 0}^{k + 1} \binom{k - i}{i - 1} - 1\\ = \sum_{i = 0}^{k} \binom{k - i}{i} + \sum_{i = 0}^{k + 1} \binom{k - i}{i - 1} \]
\[\because F_{k - 1} = \sum_{i = 0}^{k - 1} \binom{k - i - 1}{i} \\ F_{k} = \sum_{i = 0}^{k} \binom{k - i}{i} \\ F_{k + 1} = F_k + F_{k - 1} \]
\[\therefore 原等式成立 \]
11.李善兰恒等式
\[\binom{n + k}{n} ^ 2 = \sum_{j = 0}^k \binom{k}{j}^2 \binom{n + 2k - j}{2k} \]
证明：范德蒙德卷积，但这里太窄写不下了。（其实是不会）
当然，杨辉三角也可以证明。
$\mathit{Catalan}数 $
\[C_n = \frac{1}{n + 1} \cdot \binom{2n}{n} = \frac{(2n)!}{n! \cdot (n + 1)!}, \quad n \geq 0. \]
\[C_n = \binom{2n}{n} - \binom{2n}{n + 1}, \quad n \geq 0. \]
\[C_n = \frac{4n - 2}{n + 1} C_{n - 1}, \quad n > 0, \quad C_0 = 1. \]
\[C_n = \sum_{i=0}^{n-1}C_iC_{n-i-1}, \quad n > 0, \quad C_0 = 1. \]
作用：将形如3式或是4式的递推转换为1式进行快速求解。
