常用组合数公式的证明

常用组合数公式的证明

​ 证明中可能用到的一些前置知识，这里我不再给出他们证明：

$(x+y)^n=\sum_{k=0}^n{\binom{n}{k}{x}^{k}{y}^{n-k}}\tag{1}$

$\binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k}\tag{2}$

​ 上述是著名的二项式公式和帕斯卡公式，下面我们将利用他们对另外的一些组合数公式予以证明。

$k\binom{n}{k}=n\binom{n-1}{k-1}\tag{3}$

​ 将组合数公式拆开，十分显然的可以证明。

${2}^{n}=\sum_{k=0}^{n}\binom{n}{k}\tag{4}$

​ 将 $x=y=1$ 代入二项式公式可以立即得出。

$\sum_{k=0}^{n}\binom{k}{r}=\binom{n+1}{r+1}\tag{5}$

​ 考虑将 $(5)$ 式左侧展开后，于最左侧加入一项 $\binom{0}{r+1}$，且此项对于求和没有贡献，故可得到 $n+1$ 项组合数。此时使用帕斯卡公式将最左侧的两项合并，即 $\binom{0}{r+1}+\binom{0}{r}=\binom{1}{r+1}$。于是得到 $n$ 项组合数，以此类推将最左侧的两项合并，直到仅剩下一项即为 $\binom{n+1}{r+1}$。

​ 考虑组合推理求证：考虑从 $n+1$ 个球中选出 $r+1$ 个，其中 $n+1$ 个球的编号为：$1,2,...,n$。那么我们考虑一个选择，即是否选取编号为 $n+1$ 的球，现在予以讨论。假设我们选了他，那么我还需要从剩余未选取的 $n$ 个球中继续选取 $r$，所以此时的贡献为 $\binom{n}{r}$；考虑我们没有选他，那么意味着我们需要从剩余的 $n$ 个数中仍需要选取 $r+1$ 个球，那么我们可以继续考虑做一个选择，即对于是否选取编号为 $n$ 的球予以考虑。以此类推，直到无法做出选择。

${n}(x+1)^{n-1}=\sum_{k=0}^{n}{k}\binom{n}{k}{x}^{k-1}\tag{6}$

${n}{2}^{n-1}=\sum_{k=0}^{n}{k}\binom{n}{k}\tag{7}$

​ 准确的说，式 $(7)$ 是令 $x=1$ 在式 $(6)$ 代入后的结果。

​ 对于式 $(6)$ 我们可以对于 $y=1$ 时的二项式公式求导轻易得出结果。

​ 这里我们考虑使用式 $(3)$ 和式 $(4)$ 得到式 $(7)$：将式 $(4)$ 中的组合数转化成 $\binom{n}{k}=\frac{k+1}{n+1}\binom{n+1}{k+1}$，然后把分母 $n+1$ 移项到恒等式左侧，令 $n=n+1$ 且 $k=k+1$ 可得：

${n}{2}^{n-1}=\sum_{k=1}^{n}{k}\binom{n}{k}$

​ 发现此时当 $k=0$ 时得到的代数值为 $0$，因此对原式不产生贡献，即得到了式 $(7)$。

​ 运用这样的方法可以得到更多形式的恒等式，但是转化愈加繁琐，依旧建议使用求导来证明。

$\sum_{k=0}^{n}\binom{m_1}{k}\binom{m_2}{n-k}=\binom{m_1+m_2}{n}\tag{8}$

​ 上式即著名的范德蒙卷积公式。

​ 考虑组合推理求证：考虑我们可以从 $m_1$ 个红色球和 $m_2$ 个蓝色球中一共选出 $n$ 个球。此时我们枚举选出红色球的个数为 $k$，那么选出蓝色球的个数为 $n-k$，那么此时的贡献为 $\binom{m_1}{k}\binom{m_2}{n-k}$，再对所有 $k$ 的情况求和，即可得出原式。

​ 另外则可以考虑使用生成函数予以证明，这个我们放在以后再进行讨论。

$\sum_{k=0}^{n}{k}^{2}=\binom{n+2}{3}+\binom{n+1}{3}\tag{9}$

​ 这样的组合数很有趣，我们可以显然发现对于 ${m}^{2}=2\binom{m}{2}+\binom{m}{1}$。

​ 直接拆开组合数，发现 $2\binom{m}{2}+\binom{m}{1}=2\cdot\frac{m!}{2!(m-2)!}+\binom{m!}{1!(m-1)!}$，化简得到 $m(m-1)+m=m^2$，即 $2\binom{m}{2}+\binom{m}{1}=m^2$，所有原式的转化为：

$\sum_{k=0}^{n}\Bigg(2\binom{k}{2}+\binom{k}{1}\Bigg)$

​ 再加以利用式 $(5)$ 可以得到：

$2\binom{n+1}{3}+\binom{n+1}{2}$

​ 再运用帕斯卡公式可以使 $\binom{n+1}{2}+\binom{n+1}{3}=\binom{n+2}{3}$，所以得到有 $\binom{n+2}{3}+\binom{n+1}{3}$，故得原式。

​ 更有趣的是，我们都可以将 $k^n$ 的任意形式用待定系数法求出他有关组合数系数的恒等式，再进一步推理级数求和即可得出同是一个组合数系数作为结果。

​ 例如对于 $k^3$ 的情况，我们知道 $k^3=6\binom{k}{3}+6\binom{k}{2}+\binom{k}{1}$。

​ 然后可得出 $\sum_{k=0}^{n}k^3=\binom{n+3}{4}+4\binom{n+2}{4}+\binom{n+1}{4}$。

$\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k}\tag{10}$

​ 直接拆开组合数，就可以显然地得出该式。