組合公式証明及意義

(1-x)^(-r-1)=C(r,0)+C(r+1,1)x+C(r+2,2)x^2+...+C(r+k,k)x^k+....
(1-x)^(-n+m-1)=C(n-m,0)+C(n-m+1,1)x+...+C(n-m+k,k)x^k+....
兩式相乘,
左式:(1-x)^(-n+m-r -2),展開後x^m項=C(n-m+r+1 +m, m)x^m=C(n+r+1,m)x^m
而右式相乘展開後 x^m項係數=Σ[k=0~m] C(n-m+m-k, m-k)C(r+k,k)=
C(n-m+m,m)*C(r,0)+C(n-m+m-1,m-1)C(r+1,1)+...+C(n-m+m-m, m-m)C(r+m,m)
=C(n,m)C(r,0)+C(n-1,m-1)C(r+1,1)+...+C(n-m, 0)C(r+m,m)
左式x^m係數=右式x^m係數
so, C(n,m)C(r,0)+C(n-1,m-1)C(r+1,1)+...+C(n-m,0)C(r+m,m)=C(n+r+1, m)

2010-02-06 23:35:20 補充：
(1-x)^(-r-1)=C(r,0)+C(r+1,1)x+C(r+2,2)x^2+...+C(r+k,k)x^k+.... ?
中學生: by 數學歸納法
大學生: by Taylor expansion
這是離散數學,微積分or物理系常用級數(收斂範圍 -1 < x < 1, 收斂半徑 1)

2010-02-07 01:06:10 補充：
與C(n,p)C(m,0)+C(n,p-1)C(m,1)+...+C(n,0)C(m,p)=C(m+n, p)的證明方法還蠻像的!

上式可改成
C(n,n-m)*C(r,r) + C(n-1,n-m)*C(r+1,r) + C(n-2,n-m)*C(r+2,r) + ... + C(n-m,n-m)*C(r+m,r)
= C(n+r+1 , n-m+r+1)

這裡用一個比較生活化的例子來說明其意義：
全班有n+r+1個人，從1~(n+r+1)號中選出(n-m) + r + 1個人

選法一：直接選
∴全部的選法 = C(n+r+1 , n-m+r+1)


選法二：若以第(n-m+1)個人為分界，則座號在他前面的會有(n-m)個人，座號在他後面的會有r個人
第(n-m+1)個人是(n-m+1)號的選法 = C(n-m,n-m) * C(r+m,r)
第(n-m+1)個人是(n-m+2)號的選法 = C(n-m+1,n-m) * C(r+m-1,r)
第(n-m+1)個人是(n-m+3)號的選法 = C(n-m+2,n-m) * C(r+m-2,r)
......
第(n-m+1)個人是(n-m+m)號的選法 = C(n-m+m,n-m) * C(r+m-m,r) = C(n,n-m) * C(r,r)
∴全部的選法 = C(n-m,n-m)*C(r+m,r) + C(n-m+1,n-m)*C(r+m+1,r) + ... + C(n,n-m)*C(r,r)
= C(n,n-m)*C(r,r) + C(n-1,n-m)*C(r+1,r) + ... + C(n-m,n-m)*C(r+m,r)


又選法一 = 選法二
∴C(n,n-m)*C(r,r) + C(n-1,n-m)*C(r+1,r) + C(n-2,n-m)*C(r+2,r) + ... + C(n-m,n-m)*C(r+m,r)

= C(n+r+1 , n-m+r+1)
=> C(n,m)* C(r,0)+ C(n-1,m-1)* C(r+1,1)+ C(n-2,m-2)* C(r+2,2)+,,,,,,,,,+ C(n-m,0)* C(r+m,m)= C(n+r+1,m)

得證

2010-02-06 21:08:44 補充：
上面內容中
『選法二：若以第(n-m+1)個人為分界，則......』

更正為
『選法二：若選中的(n-m)+r+1個人 以第(n-m+1)個人為分界，則......』