整数分拆问题是一个古老而又十分有趣的问题。所谓整数的分拆，指将一个正整数表示为若干个正整数的和。

整数分拆理论，主要是研究各种类型的分拆函数的性质及其相互关系。早在中世纪，就有关于特殊的整数分拆问题的研究。18世纪40年代，L.欧拉提出了用母函数法（或称形式幂级数法）研究整数分拆，证明了不少有重要意义的定理，为整数分拆奠定了理论基础。解析数论中的圆法的引进，使整数分拆理论得到了进一步发展。整数分拆与模函数有密切关系，并在组合数学、群论、概率论、数理统计学及质点物理学等方面都有重要应用。

整数分拆问题是一个古老而又十分有趣的问题。所谓整数的分拆，指将一个正整数表示为若干个正整数的和。

根据是否考虑分拆部分之间的排列顺序，我们可以将整数分拆问题分为有序分拆（composition）和无序分拆（partition）。两者之间的区别如下：

在有序分拆中，考虑分拆部分求和之间的顺序。假定，之间不同的排序记为不同的方案，称之为n的有序k拆分，如3的有序2拆分为：。我们可以将这个问题建模为排列组合中的“隔板”问题，即n个无区别的球分为r份且每份至少有一个球，则需要用个隔板插入到球之间的个空隙，因此总共的方案数为。

在无序拆分中，不考虑其求和的顺序。一般假定， ，我们称之为n的无序k拆分，如3的无序k拆分为：。这种拆分可以理解为将n个无区别的球分为r份且每份至少有一个球。

一般情况下，无序拆分的个数用表示，则，，。

在通常情况下，整数分拆是指整数的无序分拆。

例1 有1克、2克、3克、4克的砝码各一枚，问能称出多少重量，并各有几种称法。

该问题可以看成n拆分成1,2,3,4之和且不允许重复的拆分数，利用母函数计算如下：

表示称出4克有2种方案，是和，以此类推，超出10克便无法称出。

例2 将14分拆成两个自然数的和，并使这两个自然数的积最大，应该如何分拆？分析与解 不考虑加数顺序，将14分拆成两个自然数的和，有共七种方法。经计算，容易得知，将14分拆成时，有最大积。

例3 将15分拆成两个自然数的和，并使这两个自然数的积最大，如何分拆？

分析与解 不考虑加数顺序，可将15分拆成下列形式的两个自然数的和：。显见，将15分拆成时，有最大积。

注：从上述两例可见，将一个自然数分拆成两个自然数的和时，如果这个自然数是偶数2m，当分拆成时，有最大积；如果这个自然数是奇数，当分拆成时，有最大积。

例4 将14分拆成3个自然数的和，并使这三个自然数的积最大，如何分拆？

分析与解 显然，只有使分拆成的数之间的差尽可能地小（比如是0或1），这样得到的积才最大。这样不难想到将14分拆成时，有最大积。

历史上，有很多关于整数拆分的研究，其中包括英国剑桥大学的G.E戈弗雷·哈代和印度学者斯里尼瓦瑟·拉马努金，拉马努拉和哈代通过自己的研究，找到了一个相关的渐进的公式，描述如下。

正整数n拆分成若干个正整数之和，其不同的拆分数用表示，的母函数为：

则拆分数估计可以表示为：

令

根据马克罗林级数：

所以：

而

又由于

所以

故

所以

但

所以

设 有

曲线是向上凸的，所以曲线 在的切线为，即有

所以

因为,由均值不等式，得

所以

整数n拆分成最大数为k的拆分数，和数n拆分成k个数的和的拆分数相等。

整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。

整数n拆分成互不相同的若干奇数的和的拆分数，和n拆分成自共轭的Ferrers图像的拆分数相等。

整数拆分可以利用渐进公式计算，随着N的无限大，整数拆分估算值接近实际值，现代还可以利用计算机的方法进行求解。在这里，主要介绍4中计算方法。

根据n和m的关系，考虑下面几种情况：

（1）当时，不论m的值为多少，只有一种划分，即；

（2）当时，不论 的值为多少（），只有一种划分，即；

（3）当时，根据划分中是否包含n，可以分为两种情况：

（a）划分中包含n的情况，只有一个，即；

（b）划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有划分；

因此，。

（4）当时，由于划分中不可能出现负数，因此就相当于f(n,n)；

（5）当时，根据划分中是否包含m，可以分为两种情况：

（a）划分中包含 的情况，即，其中的和为，可能再次出现m，因此是的m划分，因此这种划分个数为；

（b）划分中不包含m的情况，则划分中所有值都比m小，即n的划分，个数为；

因此，。

综合以上各种情况，可以看出，上面的结论具有递归定义的特征，其中（1）和（2）属于回归条件，（3）和（4）属于特殊情况，而情况（5）为通用情况，属于递归的方法，其本质主要是通过减少n或m以达到回归条件，从而解决问题。

详细递推公式描述如下：

参考源码

这个版本的时间复杂度较高，运行效率很低。

考虑到在上一节使用递归中，很多的子递归重复计算。如在计算时，划分成为 ，进一步划分为 ，接下来转换为，这样就产生了重复，然而，在递归的时候，每个都需要被计算一遍，因此可见，位于底层的状态，计算的次数也越来越多。这样在时间开销特别大，是造成运算慢的根本原因，比如算120的时候需要3秒中，计算130的时候需要27秒钟，在计算机200的时候....计算10分钟还没计算出来。

鉴于此，我们已经分析出了普通递推关系中存在大量的冗余造成了重复计算，最终导致了运行时间太长，一种自然地想法是能够用一种技巧，以避免重复计算？这里我们使用动态规划的思想进行程序设计。

在上一节中，已经分析了状态转移的方程，因此，我们在求解子问题时，利用标记的思想，首先检查产生的子问题是否在之前被计算过，这是因为对于相同的子问题，得到的结果肯定是一样的，因此利用这一步去掉冗余的操作，极大减少了计算的时间开销。对于没有标记的子问题来说，一定是没有被计算过，这样，在计算完成后，顺便标记一下子问题，以确保以后不用再重复计算。利用这个特性，可以确保所有的划分子问题都无重复，无遗漏的恰巧被计算一次。

动态规划版主要是利用了标记思想进行加速。

参考源码如下：

这样的算法效率快了很多。

对于整数拆分问题，也可以从另一个角度，即“母函数”的角度来考虑这个问题。所谓母函数，即为关于x的一个多项式，满足：

则我们称为序列 的母函数。我们从整数划分考虑，假设的某个划分中，1的出现个数记为，的个数记为，…，的个数 记为显然有：

因此 的划分数，也就是从1到 这 个数字的组合，每个数字理论上可以无限重复出现，即个数随意，使它们的和为。显然，数字 可以有如下可能，出现0次（即不出现），1次，2次，…，次等等。把数字用 表示，出现 次的数字用 表示，不出现用1表示。例如，数字2用 表示，2个2用 表示，3个2用 表示，k个2用 表示。则对于从1到 的所有可能组合结果我们可以表示为：

上面的表达式中，每个括号内的多项式代表了数字的参与到划分中的所有可能情况。因此，该多项式展开后，由于，因此 就代表了 的划分，展开后项的系数也就是的所有划分个数，即。

由此我们找到了关于整数划分的母函数，剩下的问题就是，我们需要求出 的展开后的所有系数。为此，我们首先要做多项式乘法，对于计算机编程来说，并不困难。我们把一个关于 的多项式用一个整数数组 表示，代表 的系数，然后卷积即可。

参考源码：

这样基于生成函数的方法实际上快了很多。

设第n个五边形数为，那么，即序列为：

对应图形如下：

设五边形数的生成函数为，那么有：

以上是五边形数的情况。下面是关于五边形数定理的内容：

五边形数定理是一个由欧拉发现的数学定理，描述欧拉函数展开式的特性。欧拉函数的展开式如下：

即：

可见，欧拉函数展开后，有些次方项被消去，只留下次方项为的项次，留下来的次方恰为广义五边形数。

五边形数和分割函数的关系：欧拉函数的倒数是分割函数的母函数，亦即：

其中 为 的分割函数。上式配合五边形数定理，有：

在 时，等式右侧的系数均为0，比较等式二侧的系数，可得

因此可得到分割函数的递归式：

所以，通过上面递归式，我们可以很快速地计算的整数划分方案数了。

参考代码：

以上设计的代码是最高效的。

通过比较上述四种算法，可见整数拆分的划分方法比较多样，且不同的算法运行效率差距比较大，需要仔细理解和思考。