例題：組合數之巴斯卡定理的應用
題目：將 1 至 66 的自然數分成若干群，如下(1)ˋ(2,3)ˋ(4,5,6)ˋ.....ˋ(56,57,58,......,66),
任取兩相異數,且兩數不得在同一括號內,共有多少種取法？
解答：
[quote]由 mapleaf 發表的解法
[img]http://home.pchome.com.tw/cool/mapleaf78/combi0507a.gif[/img][/quote]
我它剩下的寫完，
利用巴斯卡定理 ( C(m-1,n-1) + C(m-1,n) = C(m,n) ) 可得
所求 = C(66,2) - C(12,3) = 2145 - 2200 = 1925
除了反面解之外，我再來提供一個正面解好了，
所求 = ( C(1,1)C(65,1)+C(2,1)C(64,1)+C(3,1)C(63,1)+...+C(11,1)C(55,1) ) / 2
= ( 1×65+2×64+3×63+...+11×55) / 2
= Σk(66-k)/2 (其中 k 從 1 到 11)
= 33Σk - 1/2 Σk^2 (其中 k 從 1 到 11)
= 1925
或是，再來一個作法，一樣是正面去攻，不過不用組合數，
( 1*(2+3+4+...+11) + 2*(1+3+4+...+11) + 3*(1+2+4+...+11) + ... + 11*(2+3+4+...+10) )/2
=( 1*(1+2+3+4+...+11) + 2*(1+2+3+4+...+11) + 3*(1+2+3+4+...+11) + ... + 11*(1+2+3+4+...+11) - (1*1 + 2*2 + 3*3 +...+11*11) )/2
=( (1+2+3+4+...+11)*(1+2+3+4+...+11) - (1*1 + 2*2 + 3*3 +...+11*11) )/2
= ( (Σk)^2 - Σ(k^2) )/2 (其中，這兩個 k 都是從 1 到 11 )
= 1925
（此為原討論串[url=http://www.ck56.com/db/showthread.php?t=71271]http://www.ck56.com/db/showthread.php?t=71271[/url] 的第一題。）
頁:
[1]