为什么组合数是整数

组合数 $C_m^n={n \choose m}$ 为什么一定是整数？

我把这个问题当作一把量人的尺子：如果你斩钉截铁地回答“显然”，那我们大抵是没什么缘分的了；但如果你由此陷入了思考，那说明你属于我想结识的那类人.

免责声明：请不要通过组合数定义的角度证明，我们探讨的是纯数学推演.

---

以下证明方法来自陈景润先生著《初等数论》系列第二册.

---

引理

要证明 $C_m^n$ 是整数，我们先证明如下引理：

在 $n!$ 的标准分解式中，素数 $p$ 的方次数为

$$S=\Bigl[\dfrac{n}{p}\Bigr]+\Bigl[\dfrac{n}{p^2}\Bigr]+\cdots=\sum_{r=1}^{\infty}\Bigl[\dfrac{n}{p^r}\Bigr].$$

其中 $[x]$ 为取整函数.

当 $p^r$ 中的 $r$ 足够大时，$\Bigl[\dfrac{n}{p^r}\Bigr]=0$，故 $S$ 只含有限项数.

若 $n<p$，则 $n!$ 的分解式不含素数 $p$，此时 $S=0$，结论成立；

若 $n\geq p$，则在 $1, 2, 3, \dots, n$ 这 $n$ 个数当中：

有 $\Bigl[\dfrac{n}{p}\Bigr]$ 个 $p$ 的倍数、$\Bigl[\dfrac{n}{p^2}\Bigr]$ 个 $p^2$ 的倍数、$\Bigl[\dfrac{n}{p^3}\Bigr]$ 个 $p^3$ 的倍数……

因此恰好有 $\Bigl[\dfrac{n}{p^r}\Bigr]-\Bigl[\dfrac{n}{p^{r+1}}\Bigr]$ 个数是 $p^r$ 的倍数而不是 $p^{r+1}$ 的倍数.

这样的数在 $n!$ 的分解式中对应 $p$ 的方次数为 $r$.

因此，有：

$$\begin{aligned} S =& \Bigl(\Bigl[\dfrac{n}{p}\Bigr]-\Bigl[\dfrac{n}{p^2}\Bigr]\Bigr)+2\times\Bigl(\Bigl[\dfrac{n}{p^2}\Bigr]-\Bigl[\dfrac{n}{p^3}\Bigr]\Bigr)+\cdots \\ =& \Bigl[\dfrac{n}{p}\Bigr]+\Bigl[\dfrac{n}{p^2}\Bigr]+\cdots \\ =& \sum_{r=1}^{\infty}\Bigl[\dfrac{n}{p^r}\Bigr]. \end{aligned}$$

引理证毕.

---

证明

首先有：

$$\boxed{C_m^n=\dfrac{m!}{n!(m-n)!}\quad(n\leq m)}$$

由于 $n\leq m$，$m-n\leq m$，

所以若有素数 $p\ |\ n!(m-n)!$，必有 $p\ |\ m!$.

也就是说分母的素因子 $p$ 必定整除分子.

因此仅需要说明，在分子和分母的标准分解式中，分母中任意素数 $p$ 的方次数不大于分子中 $p$ 的方次数.

易证不等式 $[\alpha+\beta]\geq[\alpha]+[\beta]$ 对 $\forall\alpha,\beta\in\mathbb{R}$ 恒成立.

因为 $m=n+(m-n)$，故 $\Bigl[\dfrac{m}{p^r}\Bigr]\geq\Bigl[\dfrac{n}{p^r}\Bigr]+\Bigl[\dfrac{m-n}{p^r}\Bigr]$ 对 $\forall r\in\mathbb{N}$ 成立.

左右同时对 $r$ 求和，得到

$$\sum_{r=1}^{\infty}\Bigl[\dfrac{m}{p^r}\Bigr]\geq\sum_{r=1}^{\infty}\Bigl[\dfrac{n}{p^r}\Bigr]+\sum_{r=1}^{\infty}\Bigl[\dfrac{m-n}{p^r}\Bigr]$$

由之前证明的引理得到，上式左端为 $m!$ 包含素数 $p$ 的方次数，右端为 $n!$ 含素数 $p$ 的方次数与 $(m-n)!$ 含素数 $p$ 的方次数之和.

因此在 $C_m^n=\dfrac{m!}{n!(m-n)!}$ 中，分子中任意素数 $p$ 的方次数 $\geq$ 分母中 $p$ 的方次数.

故 $C_m^n$ 是整数.

证毕.

---

希望能以这个题为契机，引发大家对身边看似显而易见的结论的思考.