發新話題
打印

排列組合:六個不同物放到四個相同箱(可不放完),求方法數

推到噗浪
推到臉書

排列組合:六個不同物放到四個相同箱(可不放完),求方法數

六個不同物放到四個相同箱子,可不放完共有多少種放法?
答案855

感謝各位高手幫忙!

TOP

回復 1# anson721 的帖子

定義: 將 \(n\) 個相異物恰分成 \(k\) 堆,其方法數為 \(S(n,k)\)(註:Stirling number)

則 \(S(n,1)=1,S(n,n)=1\) 且當 \(k>n\) 時,\(S(n,k)=0\)

當 \(1\leq k\leq n\) 時,\(S(n+1,k)=S(n,k-1)+k\cdot S(n,k)\)(討論某特定物品,是否自成一堆)

運用上面的遞迴關係式,可列出如下表:



然後,可知

將六個相異物恰分成至多四堆時,其方法數為 \(1+31+90+65\)

將六個相異物選一個不放入箱子,剩下五個恰分成至多四堆,則其方法數為 \(C^6_1(1+15+25+10)\)

將六個相異物選兩個不放入箱子,剩下五個恰分成至多四堆,則其方法數為 \(C^6_2(1+7+6+1)\)

將六個相異物選三個不放入箱子,剩下五個恰分成至多四堆,則其方法數為 \(C^6_3(1+3+1)\)

將六個相異物選四個不放入箱子,剩下五個恰分成至多四堆,則其方法數為 \(C^6_4(1+1)\)

將六個相異物選五個不放入箱子,剩下五個恰分成至多四堆,則其方法數為 \(C^6_5\cdot1\)

將六個相異物全都不放入箱子,則其方法數為 \(C^6_6=1\)

所求=\((1+31+90+65)+C^6_1(1+15+25+10)+C^6_2(1+7+6+1)+C^6_3(1+3+1)+C^6_4(1+1)+C^6_5\cdot1+1\)

   \(=855.\)


感謝老王老師跟 poemghost 老師提醒我的計算錯誤,哈,原來我算式沒錯~是最後的加法加錯了!囧rz....:P

TOP

發新話題