作者cuteSquirrel (可愛的小松鼠)
看板Math
標題Re: [中學] 排列組合問題-II
時間Wed May 29 01:17:57 2024
: : (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://webptt.com/m.aspx?n=bbs/Math/M.1716916679.A.16E.html
1F：→ cuteSquirrel: Q3可視為Q4的延伸題 討論分布的基底是相同的 05/29 01:23