[問題]排列組合

[問題]排列組合

qeypour 於 星期四 五月 04, 2006 10:02 am


3相同物,5不同物分給甲,乙,丙三人,一人至少1個,一人至少2個,
一人至少3個的分法共有幾種?

qeypour
大 師
大 師
 
文章: 431
註冊時間: 2005-07-23

Re: [問題]排列組合

G@ry 於 星期四 七月 26, 2007 12:44 pm


qeypour 寫到:
3相同物,5不同物分給甲,乙,丙三人,一人至少1個,一人至少2個,
一人至少3個的分法共有幾種?

不好意思,小弟愚笨,想了很久也想不到一個簡簡單單直接代入公式的方法,只有以下這個:
[註:以下的 M(r1,r2,r3,...) = (r1+r2+r3+...)!/(r1!r2!r3!...!) 為 Multinomial coefficient 函數]

8物分給3人至少為{1,2,3}的情況有四:{1,2,5}, {1,3,4}, {2,2,4}, {2,3,3}
而由於8物中有3相同物,故此此3物的分佈情況有三:{0,0,3}, {0,1,2}, {1,1,1}

{1,2,5}:{0,0,3}有一種情況(3於5中),種數 = M(1,2,5-3) = M(1,2,2) = 30;
     {0,1,2}有四種,種數: M(1-1,2-2,5) +M(1-1,2,5-2) +M(1,2-2,5-1) +M(1,2-1,5-2)
               = 1 + 10 + 5 + 20 = 36;
     {1,1,1} = M(1-1,2-1,5-1) = 5;
{1,2,5} 加上分給不同人的組合共有 (30+36+5) x M(1,1,1) = 71 x 6 = 426;
[註:{1,5,2},{2,1,5},{2,5,1},{5,1,2},{5,2,1}為{1,2,5}的6個分給不同人的不同組合]

{1,3,4}:{0,0,3}: M(1,3-3,4) + M(1,3,4-3) = 5 + 20 = 25;
     {0,1,2}:M(1-1,3-2,4)+M(1-1,3,4-2)+M(1,3-2,4-1)+M(1,3-1,4-2)=5+10+20+30=65
     {1,1,1} = M(1-1,3-1,4-1) = 10;
{1,3,4} 分給不同人的組合共有 (25+65+10) x M(1,1,1) = 100 x 6 = 600;

{2,2,4}:{0,0,3}: M(2,2,4-3) = 30;
     {0,1,2}: 2x( M(2-2,2-1,4)+M(2-2,2,4-1)+M(2-1,2,4-2) )= 2x( 5+10+30 )= 90 ;
     {1,1,1} = M(2-1,2-1,4-1) = 20;
{2,2,4} 分給不同人的組合共有 (30+90+20) x M(2,1) = 140 x 3 = 420;

{2,3,3}:{0,0,3}: 2 x M(2,3-3,3) = 2 x 10 = 20;
     {0,1,2}: 2x( M(2-2,3-1,3)+M(2-1,3-2,3)+M(2,3-2,3-1) )= 2x( 10+20+30 )= 120 ;
     {1,1,1} = M(2-1,3-1,3-1) = 30;
{2,2,4} 分給不同人的組合共有 (20+120+30) x M(1,2) = 170 x 3 = 510;

總分法共有 426 + 600 + 420 + 510 = 1956種。 
☆子 是也

G@ry
版 主
版 主
 
文章: 597
註冊時間: 2007-03-01
來自: 香港

galaxylee 於 星期五 七月 27, 2007 1:05 am


3人至少1個
=任意分-(1人未得)-(2人未得)
=H(3,3)*3^5-C(3,1)*[H(2,3)*2^5-2]-C(3,2)
=2049種

依照(1,1,6)分給3人的分法有93種,如下:
(1)(○,○,○+5):(3!/2!)=3
(2)(△,○,○○+4):C(5,1)*3!=30
(3)(△,□,○○○+3):{[C(5,1)*C(4,1)]/2!}*3!=60
所求=2049-93=1956種

galaxylee
副教授
副教授
 
文章: 555
註冊時間: 2005-07-18

G@ry 於 星期五 七月 27, 2007 8:35 am


galaxylee 寫到:
3人至少1個
=任意分-(1人未得)-(2人未得)
=H(3,3)*3^5-C(3,1)*[H(2,3)*2^5-2]-C(3,2)
=2049種

依照(1,1,6)分給3人的分法有93種,如下:
(1)(○,○,○+5):(3!/2!)=3
(2)(△,○,○○+4):C(5,1)*3!=30
(3)(△,□,○○○+3):{[C(5,1)*C(4,1)]/2!}*3!=60
所求=2049-93=1956種

對,減回來便不用計那麼多,高手高手....
☆子 是也

G@ry
版 主
版 主
 
文章: 597
註冊時間: 2007-03-01
來自: 香港




機率及排列組合數學