Re: [中學] 排列組合問題-II (高中解法: 分組分堆)
: : (Q3) 6個不同禮物用4個相同袋子裝
用高中教的分組分堆來想也可以
要留意的細節是，
因為袋子相同，所以當有分配的禮物數量相同的時候，要扣掉重複的排列
分一份
(6) -> C(6,6) = 1
分兩份
(5,1) -> C(6,5) C(1,1) = 6
(4,2) -> C(6,4) C(2,2) = 15
(3,3) -> C(6,3) C(3,3) / 2! = 10
分三份
(4,1,1) -> C(6,4) C(2,1) C(1,1) / 2! = 15
(3,2,1) -> C(6,3) C(3,2) C(1,1) = 60
(2,2,2) -> C(6,2) C(4,2) C(2,2) / 3! = 15
分四份
(3,1,1,1) -> C(6,3) C(3,1) C(2,1) C(1,1) / 3! = 20
(2,2,1,1) -> C(6,2) C(4,2) C(2,1) C(1,1) / ( 2! * 2! ) = 45
-------------------------------------------------------------------
=> 總共 187種
: 相當於把6個禮物最多分割成四份(可以分一份、兩份、三份、四份)
: 相當於3袋空 2袋空 1袋空 袋袋都有禮物
: = S(6, 1) + S(6, 2) + S(6, 3) + S(6,4), 其中S是Stirling number的第二型
: = 1 + 31 + 90 + 65 = 187
: 遞迴通則:
: S(n,k) = n 個相異物 分成k份
: = 第n號相異物自己一堆 + 第n號相異物和別的物品同一堆
: = S(n-1, k-1) + k * S(n-1, k)
: 初始條件
: S(n, n) = 1 每個相異物各自獨立一份
: S(n, 1) = 1 每個相異物放在同一份
: : 禮物得分光, 但小朋友或是袋子未必有禮物.
: : 有點被難倒了, 煩請指導一下...
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.161.4 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1716916679.A.16E.html
→
05/29 01:23,
1年前
, 1F
05/29 01:23, 1F