定义
- 组合数，也叫二次项系数，定义为
- 下降幂： \(n\) 的 \(m\) 次下降幂定义为$$n^\underline m=n(n-1)\cdots(n-m+1)$$这样二项式系数就可以写为 $$\binom nm=\frac {n^\underline m} {m!}$$
简单应用
插板法1：
有 \(n\) 个完全相同的元素，将其分为 \(k\) 组，每组至少有一个元素，一共有多少种分法？
Sol:
组合意义：\(k-1\) 个板插入 \(n-1\) 个空隙，答案为$$\binom{n-1}{k-1}$$
插板法2：
有 \(n\) 个完全相同的元素，将其分为 \(k\) 组，每组可以为空，一共有多少种分法？
Sol:
组合意义：先加 \(k\) 个元素，使每组非空。即在插板法1基础上多加了 \(k\) 个可以使某一组为空的空隙，而板数不变。答案为$$\binom {n+k-1}{k-1}$$
插板法3：
从 \(1,2,\cdots,n\) 中选出 \(k\) 个数，要求任何两个数都不相邻，一共有多少种选法？
Sol:
组合意义：\(k\) 个元素把 \(1\sim n\) 划分成了 \(k+1\) 段，设每段的元素个数为 \(a_0,a_1,\cdots ,a_{k-1},a_{k}\)，则它们满足 $$\sum_{i=0}^{k}a_i=n-k$$由于题目要求任何两个数不相邻，那么除去两边的 \(a_0,a_k\) 可以为 \(0\)，其他所有值都已经限制不能为 \(0\)。为了使用组合数表示，我们仿照插板法2，为 \(a_0,a_k\) 加上 \(1\)，此时$$\sum_{i=0}^ka_i=n-k+2$$此时题意化归为插板法1，即：将 \(n-k+2\) 个数划分成非空的 \(k+1\) 段，答案为$$\binom{n-k+1}{k}$$
拓展定义
上述定义的定义域为 \(n,m\in N\)，后文我们将在没有特殊说明的情况下使用如下定义：
\[\binom{n}{m}=\begin{cases} \frac{n^{\underline m}}{m!} &m\ge0\\ 0 &m<0 \end{cases} \]这将定义域扩展到 \(n\in R,m\in Z\)。特别的，我们规定 \(0^0=0!=x^0=1\)。
基本恒等式
加法公式
\[\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} \]其实就是杨辉三角的递推式。
对称公式
\[\binom{n}{k}=\binom{n}{n-k},while\ n,k\in N \]组合意义很好想，\(n\) 个物品选 \(k\) 个就是 \(n\) 个物品选 \(n-k\) 个不要的物品。注意负数不成立。
吸收公式
\[k\binom{n}{k}=n\binom{n-1}{k-1},(n-k)\binom{n}{k}=n\binom{n-1}{k} \]数值的恒等依定义展开可以轻易证明，主要应用在求和式时把指标系数换成常数系数。
上指标反转
\[\binom{n}{k}=(-1)^k\binom{k-n-1}{k} \]就是按下降幂的定义展开，把分子每一项提个 \(-1\) 出来，剩下的恰好是 \(k-n-1\) 的 \(k\) 次下降幂。主要应用是逆过来处理 \((-1)^k\)。
求和恒等式
广义二项式定理
对 \(n\in R\)，\(|x|<|y|\) 有
\[(x+y)^n=\sum_{k=0}^{+\infty}\binom nkx^ky^{n-k} \]特别的，当 \(n\in N\) 时就是更常用的形式
\[(x+y)^n=\sum_{k=0}^n\binom nkx^ky^{n-k} \]对于一般形式的证明可对 \(f(x)=(x+y)^n\) 在 \(x=0\) 处做泰勒展开；对于 \(n\in N\)，则可以考虑组合意义：括号展开后 \(n\) 个 \(x\) 相乘得到 \(x^k\) 的方案数是 \(\binom nk\)，得到 \(y^{n-k}\) 的方案数是 \(\binom n {n-k}\)，而这两个方案数在 \(n\in N\) 恰好是恒等的，得证。
组合数一行之和
\[\sum_{k=0}^n\binom nk=2^n, while\ n\in N \]就是二项式定理在 \(x=y=1\) 的特例。
平行求和
\[\sum_{k=0}^n\binom {n+k}k=\binom {n+m+1}m,while\ m\in N \]可以将等式右用加法公式递归展开，即：
\[\begin{aligned} \binom{n+m+1}{m}&=\binom{n+m}{m}+\binom{n+m}{m-1}\\ &=\binom{n+m}{m}+\binom{n+m-1}{m-1}+\binom{n+m-1}{m-2}\\&=\cdots\\&=\binom{n+m}{m}+\binom{n+m-1}{m-1}+\cdots+\binom{n+1}{1}+\binom{n}{0}\\&=\sum_{k=0}^n\binom {n+k}k \end{aligned} \]得证。
上指标求和
\[\sum_{k=0}^n\binom{k}{m}=\binom{n+1}{m+1},while\ n,m\in N \]同理可以用加法公式展开：
\[\begin{aligned} \binom{n+1}{m+1}&=\binom{n}{m}+\binom{n}{m+1}\\&=\binom{n}{m}+\binom{n-1}{m}+\binom{n-1}{m+1}\\ &=\cdots\\&=\binom{n}{m}+\binom{n-1}{m}+\cdots+\binom{1}{m}+\binom{0}{m+1}\\&=\binom{n}{m}+\binom{n-1}{m}+\cdots+\binom{1}{m}+\binom{0}{m}\\&=\sum_{k=0}^n\binom{k}{m} \end{aligned} \]得证。
范德蒙德卷积
\[\sum_k\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n},while\ n\in Z \]组合意义：\(r+s\) 个物品里面选 \(n\) 个方案数就是 \(\binom{r+s}{k}\)；先在 \(r\) 个里面选 \(k\) 个，再在 \(s\) 里面选剩下 \(n-k\) 个的方案数是 \(\binom{r}{k}\binom{s}{n-k}\) 。枚举所有的 \(k\) 即有上式。
多项式系数
三项式版恒等式
\[\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k},while\ m,k\in Z \]按定义展开，数值上的相等也是显然的。我们也可以考虑组合意义：先从 \(r\) 个物品里面选 \(m\) 个，再从 \(m\) 个物品里面选 \(k\) 个的方案数即 \(\binom{r}{m}\binom{m}{k}\)，先从 \(r\) 个里面选了 \(k\) 个，再在剩下 \(r-k\) 个里选 \(m-k\) 个即 $\binom{r}{k}\binom{r-k}{m-k} $。本质上都从 \(r\) 个里选了 \(m\) 和 \(k\) 个且有 \(k\) 个是被选了两次的。
多项式系数
多项式系数是多项式 \((x_1+x_2+\cdots+x_m)^n\) 展开得到 \(x_1^{a_1},x_2^{a_2},\cdots,x_m^{a_m}\) 的系数。记做 \(\binom{n}{a_1,a_2,\cdots,a_m}=\binom{a_1+a_2+\cdots+a_m}{a_1,a_2,\cdots,a_m}\)。
组合意义：\(n\) 个两两不同的物品，分成 \(m\) 组，第 \(i\) 组有 \(a_i\) 个物品，则总方案数为
\[\frac{n!}{\prod_{i=1}^ma_i!} \]多项式系数也等于如下二项式系数乘积：
\[\binom{a_1+a_2+\cdots+a_m}{a_1,a_2,\cdots,a_m}=\binom{a_1+\cdots+a_m}{a_2+\cdots+a_m}\binom{a_2+\cdots+a_m}{a_3+\cdots+a_m} \]而三项式版恒等式也就是 \(m=3\) 的多项式系数满足的恒等式。
例题
例一
求出下式的封闭形式：$$\sum_k\binom{n}{k}^2,\ \ n\in N$$
Sol：
对称公式后范德蒙德卷积即可
例二
求出下式的封闭形式：$$\sum_kk\binom{n}{k}^2,\ \ n\in N$$
Sol：
吸收公式，对称公式后范德蒙德卷积即可
例三(来自《具体数学》)
求出下式的封闭形式：$$\sum_{k=0}^m \frac{\binom mk}{\binom nk},\ \ n,m\in N,\ n\ge m$$
Sol：
根据三项式版恒等式，有
所以上式等价于 $$\frac{1}{\binom nm}\sum_{k=0}^m\binom{n-k}{m-k}$$
用指标 \(k\) 代替 \(m-k\)，枚举次序不变；再进行平行求和，有：
例四
求出下式的封闭形式：$$\sum_{k=m}^{n} (-1)^k\binom{n}{k}\binom{k}{m},\ n,m\in N,\ n\ge m$$
Sol：
先使用三项式版恒等式 $$\sum_{k=m}^{n} (-1)^k \binom{n}{k}\binom{k}{m}=\sum_{k=m}^{n} (-1)^k\binom{n}{m}\binom{n-m}{k-m}$$
提出 \(\binom{n}{m}\)，使用上指标反转，有 $$\binom{n}{m}\sum_{k=m}^n (-1)^k \binom{n-m}{k-m}=\binom{n}{m}\sum_{k=m}^n (-1)^k (-1)^{k-m}\binom{k-n-1}{k-m}$$
消掉 \((-1)^k\)，用指标 \(k\) 替换 \(k-m\) 并修改上界，再使用平行求和，有 $$\binom{n}{m}(-1)^m \sum_{k=m}^n \binom{k-n-1}{k-m}=\binom{n}{m}(-1)^m \sum_{k=0}^{n-m} \binom{k+m-n-1}{k}=\binom{n}{m}(-1)^m \binom{0}{n-m}$$
得到答案 $$(-1)^m[n=m]$$