排列組合的證明

考慮
( 2(n+1) C n+1 ) / 2²⁽ⁿ⁺¹⁾
---------------------------------
( 2n C n ) / 2²ⁿ
= (2n+2)! / ( (2n+2 - n-1)! (n+1)! )
----------------------------------------- * 1/4
(2n)! / ( (2n - n)! n! )
=(2n+2)! / ( (n+1)! (n+1)! )
----------------------------------------- * 1/4
(2n)! / ( n! n! )
=(2n+2)! / (2n!) * ( n! / (n+1)! )² * 1/4
= (2n+1) (2n+2) * 1 / (n+1)² * 1/4
= 2(2n+1) / (n+1) * 1/4
= (2n+1) / (2n+2)

故有 (100 C 50) / 2¹ºº
= (100 C 50) / 2²⁽⁵º⁾
= (2C1)/2² * (2*1+1)/(2*1+2) * (2*2+1)/(2*2+2) * ... * (2*49+1)/(2*49+2)

= (1/2) (3/4) (5/6) ... (97/98) (99/100)

令 M = (2/3) (4/5) (6/7) ... (98/99) (100/101)
則 (100 C 50) / 2¹ºº * M = 1/101

明顯 M > (100 C 50) / 2¹ºº , 故有
( (100 C 50) / 2¹ºº )² < 1/101 < 1/100
(100 C 50) / 2¹ºº < 0.1 得所欲證。

可以輕易證明，對 n ≥ 1，

1/{2√n} ≤ C(2n, n)/2^{2n} ≤ 3/{4√(n+1)}。

取 n = 50，右邊之不等式得出：

C(100, 50)/2^{100} ≤ 3/4√(51) 約為 0.105021。

好像不夠，還可以利用 Wallis 公式進一步證明：

1/√{π[n+(1/2)]} ≤ C(2n, n)/2^{2n} ≤ 1/√{πn}。

即得 C(100, 50)/2^{100} ≤ 1/√{50π} 為約為 0.0798。

2012-04-24 20:04:26 補充：
其實，n ≥ 2 時，已有 C(2n, n)/2^{2n} ≤ 15/{64√(n+1)}。

代入 n = 50, 已得 C(2n, n)/2^{2n} ≤ 15/{64√(51)} 約為 0.0984572。