从组合数说开去

时间：2014-01-16 00:16:38 阅读：373 评论：0 收藏：0 [点我收藏+]

组合数

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

$C_{n}^{r}=\frac{n!}{r!\left( n-r \right)!}$ 是计数的时候引入的，这个数必然是整数，这是显然的。

但表达式 $\frac{n!}{r!\left( n-r \right)!}$ 为什么一定是整数呢？答案却没有那么显然。

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 !

$\frac{n!}{r!\left( n-r \right)!}=\frac{n(n-1)(n-2)(n-3)...(n-r+1)(n-r)!}{r!\left( n-r \right)!}=\frac{n(n-1)(n-2)(n-3)...(n-r+1)}{r!}$ 由组合的意义知

n?r≥0

$n-r\ge 0$ ，如果我们令

k=n?r

$k=n-r$ ，那么可以写为

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

$\frac{(k+1)(k+2)(k+3)...(k+r)}{r!}$ ，如果我们证明了这个是整数，那么组合数就必然是整数。

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

$\frac{(k+1)(k+2)(k+3)...(k+r)}{r!}k\ge 0$ 这个式子是整数，用通俗的语言来说：就是

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

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

定理一：

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

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

下面我们证明 $( k + 1 ) ( k + 2 ) ( k + 3 ) . . . ( k + r ) r ! k \geq 0$ $\frac{(k+1)(k+2)(k+3)...(k+r)}{r!}k\ge 0$ 是整数。

方法是检查素数的个数。

首先定义一个函数 E(n, p)=e, p是任意素数，e是满足 $\mathop{p}^{e}|n!$ 的最大的整数。

易知

$E(n,p)=\left\lfloor \frac{n}{p} \right\rfloor +\left\lfloor \frac{n}{{{p}^{2}}} \right\rfloor +\left\lfloor \frac{n}{{{p}^{3}}} \right\rfloor +\left\lfloor \frac{n}{{{p}^{4}}} \right\rfloor +...$

其中 $\left\lfloor {} \right\rfloor$ 表示取整函数。

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

$(k+1)(k+2)(k+3)...(k+r)=\frac{(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 ?) + . . .

$E(k+r,p)-E(k,p)=(\left\lfloor \frac{k+r}{p} \right\rfloor -\left\lfloor \frac{k}{p} \right\rfloor )+(\left\lfloor \frac{k+r}{{{p}^{2}}} \right\rfloor -\left\lfloor \frac{k}{{{p}^{2}}} \right\rfloor )+(\left\lfloor \frac{k+r}{{{p}^{3}}} \right\rfloor -\left\lfloor \frac{k}{{{p}^{3}}} \right\rfloor )+(\left\lfloor \frac{k+r}{{{p}^{4}}} \right\rfloor -\left\lfloor \frac{k}{{{p}^{4}}} \right\rfloor )+...$

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

$\left\lfloor \frac{k+r}{p} \right\rfloor =\left\lfloor \frac{k}{p}+\frac{r}{p} \right\rfloor \ge \left\lfloor \frac{k}{p} \right\rfloor +\left\lfloor \frac{r}{p} \right\rfloor ,$

这是因为

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

$\left\lfloor a+b \right\rfloor \ge \left\lfloor a \right\rfloor +\left\lfloor b \right\rfloor$ ，其中a,b为任意实数。证明比较容易，略去。

因此，

$E(k+r,p)-E(k,p)\ge \left\lfloor \frac{r}{p} \right\rfloor +\left\lfloor \frac{r}{{{p}^{2}}} \right\rfloor +\left\lfloor \frac{r}{{{p}^{3}}} \right\rfloor +\left\lfloor \frac{r}{{{p}^{4}}} \right\rfloor +...$

即

$E(k+r,p)-E(k,p)\ge E(r,p)$

也就是说，对任意的素数p， $\frac{(k+r)!}{k!}$ 中含有的p的个数均 $\ge$ r!中含有的p的个数。又由定理一知r!| $\frac{(k+r)!}{k!}$ 。

也就是说

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

$\frac{(k+1)(k+2)(k+3)...(k+r)}{r!}k\ge 0$ 是整数。

证毕。

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

证明

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

$\frac{1}{5}\mathop{n}^{5}+\frac{1}{3}\mathop{n}^{3}+\frac{7}{15}n$ 都是整数。

从组合数说开去

原文：http://www.cnblogs.com/calculus/p/3517053.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

从组合数说开去

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

定理一：

下面我们证明 (k+1)(k+2)(k+3)...(k+r)r!k≥0 \frac{(k+1)(k+2)(k+3)...(k+r)}{r!}k\ge 0 是整数。

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

下面我们证明 $( k + 1 ) ( k + 2 ) ( k + 3 ) . . . ( k + r ) r ! k \geq 0$ $\frac{(k+1)(k+2)(k+3)...(k+r)}{r!}k\ge 0$ 是整数。

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