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 的个数为。