如何证明组合数是整数

· · 个人记录

前言

其实这是某大佬的 PPT 里的一个问题，觉得很有意思，就花了一些时间想了想。

问题

总所周知，组合数的数论定义式是 \frac {(n-m+1)\times (n-m+2)\times \cdots \times n} {1\times 2\times 3\times \cdots \times m}。

那么，仅通过这个定义式，如何证明组合数一定是整数呢？

证明

感性的证明

一个组合数，可以看成是连续的 m 个正整数的积除以 m!。

那么，我们可以先找到所有 m! 的质数，从小到大分别是 p_1,p_2,p_3 \cdots p_x。

那么，我们可以考虑枚举质数。

对于质数 p_i，包含了因子 p_i 的数，在 [1,m] 中应当有 \lfloor \frac m {p_i} \rfloor 个，在 [n-m+1,n] 中也应当有 \lfloor \frac m {p_i} \rfloor 个。

那么，把这些数全部除以 p_i。

再考虑包含了因子 {p_i}^2 的数，在两个区间都应该有\lfloor \frac m {{p_i}^2} \rfloor 个，同样全部除掉。

再考虑 {p_i}^3 一直到 {p_i}^k，这样的话，我们就可以发现可以完全地把质因子 p_i 的影响消去。

所以当我们把所有的质因子全部消去时，分母就是 1，分子还剩下一些 >p_x 的质因子，所以一定是整数。

严谨的证明

上面的证明，我自己感觉比较正确，但是感觉不够数学，所以又想了一种大概是归纳法的证明方法。

我们考虑证明 m=i 的情况，假设 m<i 的情况都已经证明一定正确。

再构造两个数列 a 和 b，最开始，都是 \{1,2,3\cdots i\}。

把序列 a 的积看作分子，序列 b 的积看作分母，那么这个比值就对应某个组合数，通过把 a 整体加上一个数，来表示所有的 m=i 的组合数。

首先，原始的序列 a，对应 n=i 的情况，并且一定是整数。

现在考虑 n=i+1 的情况，也就是把序列 a 整体加上 1 的情况。

我们可以把中间 i-1 个相同的数都消去，这样序列 a 仅留下 i+1，序列 b 仅留下 1，这个显然是整数对吧，不过，我们眼光还要放长远一些，这个不就是 m=1 的组合数吗？因为 m<i 的组合数我们都看作已经证明是整数了，所以这种情况是对的。

再把序列 a 加 1，那么这一次序列 a 留下的是 \{i+1,i+2\}，序列 b 留下的是 \{1,2\}，这又对应 m=2 的组合数，也是证明过的。

再不断地把 a 加 1，可以分别对应 m=k,k\in [1,i-1] 的所有组合数情况。

但是，当 a 加了 i 次时，就没有可以对应的了，这该怎么证明呢？

可以先看看 i-1 次的时候，序列 a 是 \{i,i+1,\cdots,2\times i -1\}，序列 b 是 \{1,2,3\cdots,i\}。

因为对应了 m=i-1 的组合数，所以一定是整数，这个时候，再把序列 a 都加上 1，可以等价地看作去掉 i，加上 2\times i，所以序列 a 的积扩大了两倍，也一定是整数。

那么，再往后面继续加 1，证明方式也同理，所以我们证明得到了 m=i 的组合数都一定是整数，再继续证明 m=i+1，后续都一定可以证明，所以推广到 m 是任意数，组合数都一定是整数，证明完毕。