组合数学
排列组合——插板法：
例1：\(n\) 个相同的球，放入 \(m\) 个不同的盒子且不能有空盒存在，方案数是多少？
我们考虑使用插板法，一共 \(n\) 个球，\(n-1\) 个间隔，选出 \(m-1\) 个间隔，就可以将 \(n\) 个球分成 \(m\) 组，方案数 \(\binom{n-1}{m-1}\)
例2：\(n\) 个相同的球，放入 \(m\) 个不同的盒子，可以为空，方案数是多少？
因为可以为空，所以我们可以先借 \(m\) 个球过来，然后最后在把 \(m\) 个球拿走。
所以借球后总间隔数为 \(n+m-1\) 个，从中选 \(m-1\) 个，方案数为 \(\binom{n+m-1}{m-1}\)
同时这个等同于球 \(x_1+x_2+\cdots +x_m=n,x_i\ge 0\) 的解的方案数。
例3：\(n\) 个相同的球，放入 \(m\) 个不同的盒子且第 \(i\) 个盒子的球的数量需要大于 \(a_i\)（\(\sum a_i \le n\)），方案数是多少？
我们形式化这个问题：\(x_1+x_2+\cdots +x_m=n,(\forall i,i\in[1,n],x_i\ge a_i)\)
所以我们不妨加上给每个数减一个 \(a_i\)，就可以得到 \((x_1-a_1)+(x_2-a_2)+\cdots +(x_m-a_m)=n-\sum a_i\)
所以方案数为 \(\binom{n-\sum a_i+m-1}{m-1}=\binom{n-\sum a_i+m-1}{n-\sum a_i}\)
解释一下上面的过程，其实就是类比了 例2 的做法。
例4：\(\forall i\in[1,n],x_i\le n_i,\sum\limits_{i=1}^{k}x_i=r\) 使得这个方程有解的方案数是多少？
这个问题可以公国容斥原理来解决，具体的可以自己手推一下。
二项式定理：
首先写一下公式：
\((a+b)^n=\sum\limits_{i=0}^{n}\binom{n}{i}\cdot a^{n-i}b^i\)
对于这个公式的证明：
点击查看
我们先列举几个例子：
- \((a+b)^2=(a+b)(a+b)=a^2+2ab+b^2\)
- \((a+b)^3=(a+b)(a+b)(a+b)=a^3+3a^2b+3ab^2+b^3\)
通过找规律，我们可以看出，这个多项式的系数就是杨辉三角第 \(n+1\) 层的数。
其实也很好理解，每个系数就等于 \(n\) 个 \(a+b\) 中有多少个选了 \(a\)，方案数为 \(\binom{n}{x}\)，\(x\) 表示选 \(a\) 的数量。
所以原式 \((a+b)^n=\binom{n}{n}a^n+\binom{n}{n-1}a^{n-1}b^1+\binom{n}{n-2}a^{n-2}b^2+\cdots +\binom{n}{0}b^n\)
又可以写成 \(\sum\limits_{i=0}^{n}\binom{n}{i}a^{n-i}b^i\)