新未名空间

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

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

TheMatrix 写了： 2023年 12月 13日 17:24 我在推
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/π(σ)。

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

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

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

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

TheMatrix 写了： 2023年 12月 13日 17:24 我在推
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个板进去

Caravel 写了： 2023年 12月 14日 15:43 组合问题相对了方向就事半功倍，你这个问题用插板法，排成一排，K-1个空隙，插M-1个板进去

漂亮。一下就清楚了。

FoxMe 写了： 2023年 12月 14日 07:52 不对吧，应该是C(K+m-1,m-1)：K个弹珠排成一行，插入m-1根棒棒，把它们分成m份。

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

FoxMe 写了： 2023年 12月 14日 07:52 第二个问题应该用multinomial求解：

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

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

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

FoxMe 写了： 2023年 12月 14日 07:52 不对吧，应该是C(K+m-1,m-1)：K个弹珠排成一行，插入m-1根棒棒，把它们分成m份。

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

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

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

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

高见

changbaihou 写了： 2023年 12月 14日 17:59 这个是K表示为m个非负整数的解的个数。矩阵的是正数解个数，相当于K-m表示为m个非负整数解个数。所以你们的答案是吻合的。