正整数的无序分拆

这一篇主要来介绍有关无序分拆的计数问题。

比如，4 可以表示成如下形式：

4=4 4=3+1

4=2+2

4=2+1+1

4=1+1+1+1

因此，4 的无序分拆数就是 5。那么，对于一个任意给定的正整数 n，其无序分拆数是多少呢？

下面我将用三个算法来分别解决这个问题。

算法一：

仔细观察上面 4 的分拆，可以发现，对于一个分拆，由于是无序的，因此对这个分拆起决定作用的就是这个分拆中的最大数。那么这个最大数与正整数 n 的无序分拆数之间有什么关系呢？

设一个分拆中的最大数是 m，那么对于 n 的无序分拆，当最大数是 m 时，分拆数就等于”n-m 的分拆数“。之所以要加一个引号，是因为并不是真正的 n-m 的分拆数。因为对于 n 来说，分拆的最大数是 m，因此，n-m 的分拆中的最大数就不能超过 m。

记 F(n,m) 表示 n 的分拆中最大数为 m 的分拆个数，根据上面的分析，可以得到如下公式：

那么，n 的分拆总数 F(n) 可以用如下公式计算：

初始条件：F(n,1)=F(n,n)=1。

算法二：

在算法一中，F(n,m) 表示 n 的分拆中最大的数就是 m，那么，我们能不能放宽一下呢？记 F(n,m) 表示 n 的分拆中最大的数不超过 m。

(1) m=n：也就是 n 的分拆中，最大数不超过 n 的个数。当然，最大数为 n 的分拆只有一个，也就是它自己。除了这一个之外，最大数就不可能为 n 了，最多是 n-1 而

已。因此，求出 n 的分拆中最大数是 n-1 的分拆个数，再加上 n=n 这一个分拆，就是 F(n,n)。即 F(n,n)=1+F(n,n-1)。

(2) n(3) n>m：在 n 的分拆中，如果最大数最大可以为 m，那么这不外乎分拆中有一个或若干个 m，或者是根本就没有 m。比如，在 4 的分拆中，说最大数最大可以到 2，那么因为 4=2+2=2+1+1=1+1+1+1，于是有 m=2 的就是 2+2 与 2+1+1，完全没有 2 的则是 1+1+1+1。如果 n 的反拆中根本就没有 m，那么它的个数不就与 n 的分拆中最大数最大可以到 m-1 的个数(即 F(n,m-1) )相同吗？如果 n 的分拆中至少有一个 m，亦即 n=m+”......“，于是 n-m=”......“，所以”......“的部分正好是 n-m 的一个分拆，它的最大数最多可以到 m。因为 n-m 的分拆中最大数最多可以到 m 的有 F(n-m,m) 个，再加上 F(n,m-1)，这就是所有的情况。即 F(n,m)=F(n,m-1)+F(n-m,m)。

这样，n 的分拆数仍可用算法一中的第二个公式进行计算。

初始条件：F(n,1)=F(1,m)=1。

算法三：

在前面的两个算法中都是把注意力放在一个分拆中的最大数上，那么能不能换一个角度，看看一个分拆中的最小数与分拆个数之间是什么关系呢？

记 F(n,m) 表示将 n 分拆成 m 部分的分拆个数。考虑分拆中的最小数，如果它等于 1，那么剩下的数就被分拆成 m-1 部分，其个数为 F(n-1,m-1)；如果它不等于 1，

那么分拆成的 m 部分中的每一个数一定都大于等于 2，将这 m 部分中的每个数都减去 1，则得到一个新的分拆，即 n-m 的分拆，也是被分成 m 部分，其个数为 F(n-m,m)。根据加法原理，有 F(n,m)=F(n-1,m-1)+F(n-m,m)。

这样，n 的分拆数依然可以采用算法一中的第二个公式进行计算。

初始条件：F(n,1)=F(n,n)=1。