Re: [組合] 一組合恆等式證明
直覺上是算兩次，兩次用不同算法：在 n+m 個東西中取 k 個，
相當於在前 n 個東西先取 0 個乘以在後 m 個物品再取 k 個，
加上在前 n 個東西先取 1 個乘以在後 m 個物品再取 k-1 個，
加上在前 n 個東西先取 2 個乘以在後 m 個物品再取 k-2 個，
………
另一種常見證法是用生成函數
n+m n m
(1+x) = (1+x) (1+x) 兩邊分別用二項式定理乘出來
n+m n+m k n n i m m j
Σ( )x = [ Σ( )x ][ Σ( )x ] 右邊乘開
k=0 k i=0 i j=0 j
n+m k n m k
= Σ[ Σ( )( ) ]x
k=0 i=0 i k-i
左右相等，得證。
這個組合恆等式名字叫 Vandermonde's idendity，有興趣可以看
http://en.wikipedia.org/wiki/Vandermonde's_identity
※ 引述《iddee (人生失敗組)》之銘言：
: 試證：
: n
: C(n+m,k) = Σ [C(n,i) * C(m,k-i)]
: i=0
: 其中 0 <= k <= n+m，且 n,m 是非負整數。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.33.98
推
08/29 18:04, , 1F
08/29 18:04, 1F