如何用组合数学证明 (n²)! 能被 (n!)^(n＋1) 整除？ 第1页

我被这道题惊了。

一开始，我以为它是一道「数论题」，于是想用素数的方法来做，于是我写下了：

对任意不大于 n 的素数 p，记 为 n! 分解质因数时 p 的阶（也即： n! 能被 整除，但是不能被 整除）
那么，原题等价于证明，对于所有不大于 n 的素数 p，有
易见， (Legendre’s Formula)
于是原命题等价于证明，对于所有不大于 n 的素数 p，
有
……

然后我就发现，好像有点复杂，细节很多，即使证明了也不优雅。

然后，我发现了四个大字

组！合！数！学！

于是，我转变思路，反向构造了这个组合题的场景，构造出一道题：

有 个人，分成 n 组，每组 n 人，请问一共有多少种分法？

解：

先把这 个人排成 n*n 的矩阵，共有 种排法。

假如每一列的人算组成一队，共分成 n 队，那么：

• 在每一队中，这 n 个人的顺序都是无所谓的，所以算组合数时在每一队中都需要除以 n！；
• 对于这 n 队之间来说，两两的顺序也是无所谓的，所以算组合数时需要再除以 n！。

于是，组队的总方案数是：

这个数必须是整数，因此原题得证！