作者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/cn.aspx?n=bbs/Math/M.1716916679.A.16E.html
1F:→ cuteSquirrel: Q3可视为Q4的延伸题 讨论分布的基底是相同的 05/29 01:23