为什么组合数是整数

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

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

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


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


引理

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

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

其中 $[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$.

因此,有:

引理证毕.


证明

首先有:

由于 $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$ 求和,得到

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

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

故 $C_m^n$ 是整数.

证毕.


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

本文作者:Xecades

本文链接:https://blog.xecades.xyz/articles/combination/

文章默认使用 CC BY-NC-SA 4.0 协议进行许可,使用时请注意遵守协议。

评论