一个partition组合问题

[TheMatrix]

我在推
m partition of K
的个数，counting order，也就是比如(3,1,1)不等于(1,3,1)。

网络给我的答案是C(K-1,m-1)，就是K-1 choose m-1。这么简单？对不对啊？

[TheMatrix]

我在推
m partition of K
的个数，counting order，也就是比如(3,1,1)不等于(1,3,1)。

网络给我的答案是C(K-1,m-1)，就是K-1 choose m-1。这么简单？对不对啊？

对的。用归纳法不难证明。

再引申一个问题：
Let P(m,K) be the set of m partition of K, counting order,
也就是，P(m,K)={σ:[1..m]->[1..K], σ(1)+σ(2)+...+σ(m)=K}
把每一个partition的数乘起来：π(σ)=σ(1)*σ(2)...σ(m)
给定m,K，求
sum {for σ in P(m,K)} 1/π(σ)。

[FoxMe]

不对吧，应该是C(K+m-1,m-1)：K个弹珠排成一行，插入m-1根棒棒，把它们分成m份。

第二个问题应该用multinomial求解：

https://en.wikipedia.org/wiki/Multinomial_theorem

真巧，最近我也在思考类似的问题。

[Caravel]

我在推
m partition of K
的个数，counting order，也就是比如(3,1,1)不等于(1,3,1)。

网络给我的答案是C(K-1,m-1)，就是K-1 choose m-1。这么简单？对不对啊？

组合问题相对了方向就事半功倍，你这个问题用插板法，排成一排，K-1个空隙，插M-1个板进去

[TheMatrix]

组合问题相对了方向就事半功倍，你这个问题用插板法，排成一排，K-1个空隙，插M-1个板进去

漂亮。一下就清楚了。

[TheMatrix]

不对吧，应该是C(K+m-1,m-1)：K个弹珠排成一行，插入m-1根棒棒，把它们分成m份。

你这个方法和Caravel的方向是一样的。K+m-1的逻辑可能有问题。

第二个问题应该用multinomial求解：

https://en.wikipedia.org/wiki/Multinomial_theorem

真巧，最近我也在思考类似的问题。

我第二个问题差不多是从multinomial反过来提出来的。从formal展开ln(n)^m出来的。

[changbaihou]

不对吧，应该是C(K+m-1,m-1)：K个弹珠排成一行，插入m-1根棒棒，把它们分成m份。

第二个问题应该用multinomial求解：

https://en.wikipedia.org/wiki/Multinomial_theorem

真巧，最近我也在思考类似的问题。

这个是K表示为m个非负整数的解的个数。矩阵的是正数解个数，相当于K-m表示为m个非负整数解个数。所以你们的答案是吻合的。

[FoxMe]

高见

这个是K表示为m个非负整数的解的个数。矩阵的是正数解个数，相当于K-m表示为m个非负整数解个数。所以你们的答案是吻合的。