从组合数说开去

2023-10-16 16:49:22

组合数

C r n = n ! r ! ( n ? r ) !

是计数的时候引入的，这个数必然是整数，这是显然的。

但表达式n! 从组合数说开去 r!(n?r)! 为什么一定是整数呢？答案却没有那么显然。

n ! r ! ( n ? r ) ! = n ( n ? 1 ) ( n ? 2 ) ( n ? 3 ) . . . ( n ? r + 1 ) ( n ? r ) ! r ! ( n ? r ) ! = n ( n ? 1 ) ( n ? 2 ) ( n ? 3 ) . . . ( n ? r + 1 ) r !

由组合的意义知

n?r≥0

，如果我们令

k=n?r

，那么可以写为

( k + 1 ) ( k + 2 ) ( k + 3 ) . . . ( k + r ) r !

，如果我们证明了这个是整数，那么组合数就必然是整数。

( k + 1 ) ( k + 2 ) ( k + 3 ) . . . ( k + r ) r ! k \geq 0

这个式子是整数，用通俗的语言来说：就是

n个连续非负整数的积可以被n的阶乘整除。

在证明之前，我们先看一个定理

每个≥2的正整数要么是素数，要么是一些素数的乘积。

这个定理很好证明，可以用最小整数公理，也可以用第二数学归纳法。

方法是检查素数的个数。

首先定义一个函数 E(n, p)=e, p是任意素数，e是满足p 从组合数说开去 e|n! 的最大的整数。

易知

E(n,p)=?n 从组合数说开去 p?+?np2?+?np3?+?np4?+...

其中 ?? 从组合数说开去表示取整函数。

(k + 1) (k + 2) (k + 3) . . . (k + r) = ( k + r ) ! k !

对任意的素数p

E (k + r, p) ? E (k, p) = (? k + r p ? ? ? k p ?) + (? k + r p 2 ? ? ? k p 2 ?) + (? k + r p 3 ? ? ? k p 3 ?) + (? k + r p 4 ? ? ? k p 4 ?) + . . .

? k + r p ? = ? k p + r p ? \geq ? k p ? + ? r p ?,

这是因为

? a + b ? \geq ? a ? + ? b ?

，其中a,b为任意实数。证明比较容易，略去。

因此，

E(k+r,p)?E(k,p)≥?r 从组合数说开去 p?+?rp2?+?rp3?+?rp4?+...

即

E(k+r,p)?E(k,p) 从组合数说开去 ≥E(r,p)

也就是说，对任意的素数p，(k+r)! 从组合数说开去 k! 中含有的p的个数均 ≥ r!中含有的p的个数。又由定理一知r!| (k+r)!k! 。

也就是说

( k + 1 ) ( k + 2 ) ( k + 3 ) . . . ( k + r ) r ! k \geq 0

是整数。

证毕。

证明

1 5 n 5 + 1 3 n 3 + 7 15 n

都是整数。