一个正整数 n 的 (strict) composition 是把 n 写成一个正整数数列的和的形式。
举例,正整数 4 可以拆分成
一共 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 的个数就等于 。
如果把 0 也算做一个部分,那么我们叫它 weak composition 。我们不能定义一个正整数 n 一共有多少种 weak composition ,因为可以有无限多个 0 相加;但是我们能得知当把 n 分成 k 个部分的时候,一共有多少种 weak composition 。例如,当 n = 4 的时候,如果把 4 分成 2 个部分,那么一共有 5 种 weak composition ,如下:
如何得知当把一个正整数 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 ?
1
pangtianyu OP 难道 V2EX 上面没有对这种感兴趣的嘛 0.0
|
2
di00di 2016-05-23 21:09:19 +08:00 2
可以按照这个思路解:
step1. 算出没有约束也就是每个部分可以是 1 到 n 的解 step2. 计算 k 个部分大于等于 m + 1 的解。此步计算可以作变量替换相当于把 n-k*(m+1)分成 k 个部分的解 step3. 根据容斥原理计算出最后的解。 |
3
nsqiang 2018-01-29 09:32:44 +08:00
@pangtianyu 问题解决了么~
|
4
nsqiang 2018-01-29 10:04:14 +08:00
|
5
nsqiang 2018-01-29 10:19:49 +08:00
|
7
pangtianyu OP @nsqiang #6 哈哈才看到不好意思 已经解决了 这是我一次数学课 final exam 的问题 我做了不太确定想来问问
|