关于组合数学和整数拆分的问题

[pangtianyu]

Composition

Strict Composition

一个正整数 n 的 (strict) composition 是把 n 写成一个正整数数列的和的形式。
举例，正整数 4 可以拆分成

• 4
• 3 + 1
• 1 + 3
• 2 + 2
• 2 + 1 + 1
• 1 + 2 + 1
• 1 + 1 + 2
• 1 + 1 + 1 + 1

一共 8 种 composition 。注意顺序不同是有所谓的。

如何数一个正整数 n 有多少种 composition 呢？首先，一个正整数 n 可以变成 n 个 1 相加的形式。所以，我们可以先写出一个带有 n 个 1 的数列：

1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ ... 1 _ 1 _ 1 _ 1

中间的空格保留留空。在空格中我们可以填入逗号「,」或者加号「+」。填入不同的逗号或者加号，我们就会组成不同的 composition 。所以，问题变成了有多少种方式去填入逗号。如果逗号的位置确定了，加号的位置也就会跟着确定。在这里，假设我们要把 n 分成 k 个部分，那么我们就需要填入 k-1 个逗号。我们现在知道一共有 n-1 个空格可以填。所以，一共有 种方式去填入逗号（详见组合）。这也就相当于把 n 分成 k 个部分的时候，一共有 种 composition 的样子。最少我们能分成 1 个部分，就是 n 自己本身；而最多我们能分成 n 个部分，也就是 n 个 1 相加。所以，对于一个 n 来讲，它的 composition 的个数就等于 。

Weak Composition

如果把 0 也算做一个部分，那么我们叫它 weak composition 。我们不能定义一个正整数 n 一共有多少种 weak composition ，因为可以有无限多个 0 相加；但是我们能得知当把 n 分成 k 个部分的时候，一共有多少种 weak composition 。例如，当 n = 4 的时候，如果把 4 分成 2 个部分，那么一共有 5 种 weak composition ，如下：

• 3 + 1
• 2 + 2
• 1 + 3
• 0 + 4
• 4 + 0

如何得知当把一个正整数 n 拆分成 k 个部分的时候有多少种 weak composition ？首先，把 n 想象成 n 个 1 ，如果要把 n 个 1 组成的数列分成 k 个部分，那么我们需要有 k-1 个隔板。举例:当 n = 9, k = 4 的时候，其中一种情况是： 1 1 1 1 ｜ 1 1 ｜｜ 1 1 1 ，也就是 4 + 2 + 0 + 3 。所以问题可以变成：一共有 n + (k - 1) 个物体组成一个数列，把其中 n 个物体变成 1 ，其余 k - 1 个物体变成隔板，一共有多少种方法？这里如果 n 个 1 的位置确定了，余下的隔板位置也就确定了，反之也是如此。所以，有 方法。综上，可以得出结论，把一个正整数 n 拆分成 k 个部分， weak composition 的个数为 。

问题来了

问题 1 ：如果要把 n 分成 k 个部分，但是每个部分不能大于 m ，请问一共有多少种 composition ？ 举例，当 n = 4, k = 2, m = 2 的时候，整数 4 的 composition 只有一个： 2 + 2 。

问题 2 ：要把 n 分成 k 个部分，但是每个部分不能大于 m ，请问一共有多少种 weak composition ？

[pangtianyu]

难道 V2EX 上面没有对这种感兴趣的嘛 0.0

[di00di]

可以按照这个思路解：
step1. 算出没有约束也就是每个部分可以是 1 到 n 的解
step2. 计算 k 个部分大于等于 m ＋ 1 的解。此步计算可以作变量替换相当于把 n-k*(m+1)分成 k 个部分的解
step3. 根据容斥原理计算出最后的解。

[nsqiang]

@pangtianyu 问题解决了么~

[nsqiang]

@pangtianyu http://blog.csdn.net/u013445530/article/details/48034941 这篇有个博客类似~

[nsqiang]

@pangtianyu https://math.stackexchange.com/questions/89417/number-of-ways-to-put-n-unlabeled-balls-in-k-bins-with-a-max-of-m-balls-in?rq=1 找到~

[nsqiang]

@nsqiang 收藏~

[pangtianyu]

@nsqiang #6 哈哈才看到不好意思 已经解决了 这是我一次数学课 final exam 的问题 我做了不太确定想来问问