發新話題
打印

例題:組合數之巴斯卡定理的應用

推到噗浪
推到臉書

例題:組合數之巴斯卡定理的應用

題目:將 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 的第一題。)

TOP

發新話題