正文
组合数
本文为转载的文章，转载自：组合 - hfjh
默认会组合数基础内容和二项式定理
学习之前你应该知道：
广义组合数定义
\[\binom n m = \frac {n^{\underline m}} {m!}
\]
\[n^{\underline m} = n \times(n - 1) \times (n - 2)\times...\times(n-m+1)
\]
主要内容
组合数常用公式及证明
这里的证明主要分为 3 种
1.用组合意义证明
2.用定义证明(拆成阶乘形式)
3.用前面的公式推导
公式目录
\[\begin{aligned}
\binom n k &= \frac n k \binom {n - 1} {k - 1}\\
\binom n k &= (-1)^k \binom {k - n - 1}{k}\\
\binom nm\binom mk &= \binom nk \binom {n-k}{m-k}\\
\binom nk &= \binom {n - 1}{k - 1} + \binom {n - 1}{k}\\
\sum_{k = 0}^n \binom km &= \binom{n + 1} {m + 1}\\
\sum_{k = 0}^m \binom {n+k}k &= \binom {n + m + 1} m\\
\sum_{k = 0}^{n}\binom r k\binom s {n - k} &= \binom {r + s}{n}\\
\sum_{k = 0}^n\binom n k &= 2^n\\
\sum_{k = 0}^m(-1)^k \binom n k &= (-1)^m\binom {n - 1}m\\
\end{aligned}
\]
不带求和
1.吸收公式（Absorption Identity）：
\[\binom n k = \frac n k \binom {n - 1} {k - 1}
\]
定义证明：
\[\binom n k = \frac {n!}{(k-n)!\times k!}
\]
\[\frac n k \binom {n - 1}{k - 1}
= \frac n k \frac {(n - 1)!}{(n-k)!\times(k-1)!}
= \frac {n!}{(k-n)!\times k!}
\]
推广：
\[k\binom n k = n \binom {n-1}{k-1},(n - k)\binom n k = n \binom{n-1} k
\]
均可用定义证明，不再赘述。
2.上指标反转（Negating the Upper Index）：
\[\binom n k = (-1)^k \binom {k - n - 1}{k}
\]
定义证明：
（这里运用组合数广义定义）
\[\binom {k - n - 1} k = \frac {(k - n - 1) ^ {\underline k}} {k!}\\
\begin{aligned}
(k - n - 1) ^ {\underline k} &= (k - n - 1)\times(k - n - 2)\times...\times(-n)\\
&=(-1)^k \times n \times (n +(k - 1) - k) \times ...\times (n + 1 - k)\\
&=(-1)^k n ^{\underline k}
\end{aligned}
\]
把这个带入就可以了。
3.三项式系数恒等式：
\[\binom nm\binom mk = \binom nk \binom {n-k}{m-k}
\]
组合意义证明：
从 \(n\) 个小球中选 \(m\) 个染成红色，再从 \(m\) 个红色小球中选 \(k\) 个染成蓝色。
从 \(n\) 个小球中选 \(k\) 个染成蓝色，再从 \(n - k\) 个无色小球中选 \(m - k\) 个染成红色。
两种方法得到的最终结果等价。
定义证明：
\[\binom nm\binom mk = \frac {n!}{m!\times(n-m)!} \times \frac{m!}{k!\times(m-k)!}
= \frac {n!} {k!\times(n-m)!\times(m-k)!}
\]
\[\binom nk\binom {n-k}{m-k} = \frac {n!}{k!\times(n-k)!} \times
\frac{(n-k)!}{(n-m)!\times(m-k)!}
= \frac {n!} {k!\times(n-m)!\times(m-k)!}
\]
4.帕斯卡公式
\[\binom nk = \binom {n - 1}{k - 1} + \binom {n - 1}{k}，k\in[1,n]
\]
组合意义证明
从 \(n\) 个小球中选 \(k\) 个，一定是最后一个小球不选然后从 \(n - 1\) 个里面选 \(k\) 个和最后一个小球要选然后从 \(n - 1\) 个里面选 \(k - 1\) 个的方案数加起来。
定义证明
\[\begin{aligned}
\binom nk &= \binom {n - 1}{k - 1} + \binom {n - 1}{k}\\
\frac {n!} {k!\times(n-k)!} &= \frac {(n-1)!}{(n-k)!\times(k-1)!} +
\frac {(n-1)!}{(n-k - 1)!\times(k)!}\\
\frac {n!} {k!\times(n-k)!} &= \frac {(n-1)!\times(k)!\times(n-1-k)! + (n-k)!\times(n-1)!\times(k-1)!}
{(n-k)!\times(k-1)!\times k!\times(n-1-k)!}\\
{n!}&= \frac {(n-1)!\times[(k)!\times(n-1-k)! + (n-k)!\times(k-1)!]}
{(k-1)!\times(n-1-k)!}\\
n &= \frac{k! \times (n-1-k)!} {(k-1)!\times(n-1-k)!}
+ \frac{(n-k)! \times (k-1)!} {(k-1)!\times(n-1-k)!}\\
n &= k + n - k\\
n &= n
\end{aligned}
\]
求和
接下来才是真正有用的东西
1.上指标求和（Summation on the Upper Index）：
公式1
\[\sum_{k = 0}^n \binom km = \binom{n + 1} {m + 1}\\
\]
组合证明
有 \(n + 1\) 个球，选 \(m + 1\) 个，枚举最后一个选的位置在 \(k + 1\) 则前 \(k\) 个要选 \(m\) 个。
推导证明
根据4.帕斯卡公式得
\[\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}\\
&=\binom{n}{m}+\binom{n-1}{m} + \binom{n-2}{m} + \binom{n-2}{m+1}\\
&=......\\
&=\sum_{k = 0}^n \binom km
\end{aligned}
\]
公式2
\[\sum_{k = 0}^m \binom {n+k}k = \binom {n + m + 1} m
\]
推导证明
\[\begin{aligned}
\sum_{k = 0}^m \binom {n+k}k &= \sum_{k = 0}^m \binom {n+k}n
=\sum_{k = n}^{n + m} \binom kn\\
&=\sum_{k = 0}^{n + m} \binom kn - \sum_{k = 0}^{n-1} \binom kn\\
&=\binom {m + n + 1}{n + 1} - \binom{n}{n + 1}\\
&=\binom {m + n + 1}m
\end{aligned}
\]
第 3 行运用了上指标求和的公式1 ，第 3 行还使用了\(\binom n {n + 1} = 0\)
2.范德蒙德卷积
\[\sum_{k = 0}^{n}\binom r k\binom s {n - k} = \binom {r + s}{n}
\]
组合证明
有 \(r + s\) 个小球选 \(n\) 个小球，枚举在前 \(r\) 个中选 \(k\) 个，在后 \(s\) 个中选 \(n-k\) 个。
推导证明
这里用了二项式定理
\[\begin{aligned}
\sum_{k=0}^{n+m}\binom{n+m}kx^k&= (x + 1)^{n + m}\\
&=(x + 1)^n(x + 1)^m\\
&=\sum_{r=0}^n \binom nr x^r + \sum_{r=0}^m \binom ms x^s\\
&=\sum_{k=0}^{n+m}\sum_{r=0}^k\binom{n}{k}\binom{m}{k-r}x^k
\end{aligned}
\\
\Rightarrow \binom{n+m}k = \sum_{r=0}^k\binom{n}{k}\binom{m}{k-r}
\]
3.一行之和
\[\sum_{k=0}^n\binom n k = 2^n
\]
组合意义证明
从 \(n\) 个小球里面选任意个小球，每个小球有选和不选两种情况。
即是所有子集的个数。
推导证明
这里使用帕斯卡公式，以及数学归纳法。
首先在 \(n = 0\) 时只有 \(\binom 00 = 1\)，满足 \(= 2^0\)
于是对于 \(n\) 时，假设 \(\sum_{k = 0}^{n - 1} {n - 1 \choose k} = 2^{n-1}\) 成立。
\[\begin{aligned}
\sum_{k=0}^n\binom n k
&= \binom n0 + \sum_{k = 1}^n ({n - 1 \choose k} + {n - 1 \choose k - 1}) \\
&= \binom n0 + \sum_{k = 1}^n {n - 1 \choose k} + \sum_{k = 1}^n {n - 1 \choose k - 1} \\
&= \binom n0 + \sum_{k = 1}^n {n - 1 \choose k} + \sum_{k = 0}^n {n - 1 \choose k} \\
&= \binom n0 + \binom {n-1}0 + \binom{n-1}n + 2 \sum_{k = 1}^{n - 1} {n - 1 \choose k} \\
&= 2 \binom n0 + 2 \sum_{k = 1}^{n-1} {n - 1 \choose k } \\
&= 2 \sum_{k = 0}^{n - 1} {n - 1 \choose k} \\
&= 2 \times 2^{n - 1} \\
&= 2^n
\end{aligned}
\]
依据归纳法，假设成立。
4.交错和
\[\sum_{k=0}^m(-1)^k \binom n k = (-1)^m\binom {n - 1}m
\]
推导证明
\[\begin{aligned}
\sum_{k=0}^m(-1)^k \binom r k
&= \sum_{k=0}^m\binom {k-n-1}k\\
&= \binom{m-n}{m}\\
&=(-1)^m\binom {n - 1} m
\end{aligned}
\]
运用上指标反转和上指标求和
