題目:將 1 至 66 的自然數分成若干群,如下
(1)ˋ(2,3)ˋ(4,5,6)ˋ.....ˋ(56,57,58,......,66),
任取兩相異數,且兩數不得在同一括號內,共有多少種取法?
解答:
引用:
由 mapleaf 發表的解法
我它剩下的寫完,
利用巴斯卡定理 ( 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
(此為原討論串
http://www.ck56.com/db/showthread.php?t=71271 的第一題。)