更新时间：2024-06-12 16:46
整数分拆理论，主要是研究各种类型的分拆函数的性质及其相互关系。早在中世纪，就有关于特殊的整数分拆问题的研究。18世纪40年代，L.欧拉提出了用母函数法（或称形式幂级数法）研究整数分拆，证明了不少有重要意义的定理，为整数分拆奠定了理论基础。解析数论中的圆法的引进，使整数分拆理论得到了进一步发展。整数分拆与模函数有密切关系，并在组合数学、群论、概率论、数理统计学及质点物理学等方面都有重要应用。
整数分拆问题是一个古老而又十分有趣的问题。所谓整数的分拆，指将一个正整数表示为若干个正整数的和。
根据是否考虑分拆部分之间的排列顺序，我们可以将整数分拆问题分为有序分拆（composition）和无序分拆（partition）。两者之间的区别如下：
在有序分拆中，考虑分拆部分求和之间的顺序。假定 ， 之间不同的排序记为不同的方案，称之为n的有序k拆分，如3的有序2拆分为：3=1+2=2+1。我们可以将这个问题建模为排列组合中的“隔板”问题，即n个无区别的球分为r份且每份至少有一个球，则需要用r-1个隔板插入到球之间的n-1个空隙，因此总共的方案数为C(n-1,r-1)。
在无序拆分中，不考虑其求和的顺序。一般假定 ， ，我们称之为n的无序k拆分，如3的无序k拆分为：3=1+2。这种拆分可以理解为将n个无区别的球分为r份且每份至少有一个球。
一般情况下，无序拆分的个数用 p(n) 表示，则 p(2)=1，p(3)=2，p(4)=5。
在通常情况下，整数分拆是指整数的无序分拆。
例1 有1克、2克、3克、4克的砝码各一枚，问能称出多少重量，并各有几种称法。
该问题可以看成n拆分成1,2,3,4之和且不允许重复的拆分数，利用母函数计算如下：
表示称出4克有2种方案，是1+3和4，以此类推，超出10克便无法称出。
例2 将14分拆成两个自然数的和，并使这两个自然数的积最大，应该如何分拆？分析与解 不考虑加数顺序，将14分拆成两个自然数的和，有1+13，2+12，3+11，4+10，5+9，6+8，7+7共七种方法。经计算，容易得知，将14分拆成7+ 7时，有最大积7×7=49。
例3 将15分拆成两个自然数的和，并使这两个自然数的积最大，如何分拆？
分析与解 不考虑加数顺序，可将15分拆成下列形式的两个自然数的和：1+14，2+13，3+12，4+11，5+10，6+9，7+8。显见，将15分拆成7+8时，有最大积7×8=56。
注：从上述两例可见，将一个自然数分拆成两个自然数的和时，如果这个自然数是偶数2m，当分拆成m+m时，有最大积m×m=m2；如果这个自然数是奇数2m+1，当分拆成m+（m+1）时，有最大积m×（m+1）。
例4 将14分拆成3个自然数的和，并使这三个自然数的积最大，如何分拆？
分析与解 显然，只有使分拆成的数之间的差尽可能地小（比如是0或1），这样得到的积才最大。这样不难想到将14分拆成4+5+5时，有最大积4×5×5=100。
历史上，有很多关于整数拆分的研究，其中包括英国剑桥大学的G.E哈代和印度学者拉马努金，拉马努拉和哈代通过自己的研究，找到了一个相关的渐进的公式，描述如下。
正整数n拆分成若干个正整数之和，其不同的拆分数用p(n)表示，{p(n)}的母函数为：
则拆分数估计可以表示为：
令
根据马克罗林级数：
所以：
而
又由于
所以
故
所以
但
所以
设 有
曲线 y = lnx 是向上凸的，所以曲线 y = lnx 在（1,0）的切线为 y = x-1 ，即有
所以
对于 求极小值：
因为，由均值不等式，得
所以
整数n拆分成最大数为k的拆分数，和数n拆分成k个数的和的拆分数相等。
整数n拆分成最多不超过m个数的和的拆分数，和n拆分成最大不超过m的拆分数相等。
整数n拆分成互不相同的若干奇数的和的拆分数,和n拆分成自共轭的Ferrers图像的拆分数相等。
整数拆分可以利用渐进公式计算，随着N的无限大，整数拆分估算值接近实际值，现代还可以利用计算机的方法进行求解。在这里，主要介绍4中计算方法。
根据n和m的关系，考虑下面几种情况：
（1）当n=1时，不论m的值为多少（m＞0），只有一种划分，即{1}；
（2）当m=1时，不论 的值为多少（n＞0），只有一种划分，即{1,1,....1,1,1}；
（3）当n=m时，根据划分中是否包含n，可以分为两种情况：
（a）划分中包含n的情况，只有一个，即{n}；
（b）划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有（n-1）划分；
因此，f(n,n) = 1 + f(n, n - 1)。
（4）当n＜m时，由于划分中不可能出现负数，因此就相当于f(n,n)；
（5）当n＞m时，根据划分中是否包含m，可以分为两种情况：
（a）划分中包含 的情况，即{m,{x1,x2,x3,...,xi}}，其中{x1,x2,x3,...,xi}的和为n-m，可能再次出现m，因此是（n-m）的m划分，因此这种划分个数为f(n-m,m)；
（b）划分中不包含m的情况，则划分中所有值都比m小，即n的（m-1）划分，个数为f(n,m-1)；
因此，f(n,m)=f(n-m,m)+f(n,m-1) 。
综合以上各种情况，可以看出，上面的结论具有递归定义的特征，其中（1）和（2）属于回归条件，（3）和（4）属于特殊情况，而情况（5）为通用情况，属于递归的方法，其本质主要是通过减少n或m以达到回归条件，从而解决问题。
详细递推公式描述如下：
参考源码
考虑到在上一节使用递归中，很多的子递归重复计算。如在计算 f (10,9)时，划分成为 f (1,9) + f (10,8)，进一步划分为 f (1,1)=f (2,8)+f (10,7)，接下来转换为f (1,1) +f (2,2)+ f (3,7)+ f (10,6) =3* f (1,1) +1+ f (3,7)+ f (10,6)，这样就产生了重复，然而，在递归的时候，每个都需要被计算一遍，因此可见，位于底层的状态，计算的次数也越来越多。这样在时间开销特别大，是造成运算慢的根本原因，比如算120的时候需要3秒钟，计算130的时候需要27秒钟，在计算机200的时候....计算10分钟还没计算出来。
鉴于此，我们已经分析出了普通递推关系中存在大量的冗余造成了重复计算，最终导致了运行时间太长，一种自然地想法是能够用一种技巧，以避免重复计算？这里我们使用动态规划的思想进行程序设计。
在上一节中，已经分析了状态转移的方程，因此，我们在求解子问题时，利用标记的思想，首先检查产生的子问题是否在之前被计算过，这是因为对于相同的子问题，得到的结果肯定是一样的，因此利用这一步去掉冗余的操作，极大减少了计算的时间开销。对于没有标记的子问题来说，一定是没有被计算过，这样，在计算完成后，顺便标记一下子问题，以确保以后不用再重复计算。利用这个特性，可以确保所有的划分子问题都无重复，无遗漏的恰巧被计算一次。
动态规划版主要是利用了标记思想进行加速。
参考源码如下：
这样的算法效率快了很多。
对于整数拆分问题，也可以从另一个角度，即“母函数”的角度来考虑这个问题。所谓母函数，即为关于x的一个多项式 ，满足：
则我们称为序列 的母函数。我们从整数划分考虑，假设的某个划分中，1的出现个数记为 ，2的个数记为 ，…， 的个数 记为显然有：
因此 的划分数，也就是从1到 这 个数字的组合，每个数字理论上可以无限重复出现，即个数随意，使它们的和为 。显然，数字 可以有如下可能，出现0次（即不出现），1次，2次，…， 次等等。把数字用 表示，出现 次的数字用 表示，不出现用1表示。例如，数字2用 表示，2个2用 表示，3个2用 表示，k个2用 表示。则对于从1到 的所有可能组合结果我们可以表示为：
上面的表达式中，每个括号内的多项式代表了数字的参与到划分中的所有可能情况。因此，该多项式展开后，由于 ，因此 就代表了 的划分，展开后项的系数也就是的所有划分个数，即 。
由此我们找到了关于整数划分的母函数 ，剩下的问题就是，我们需要求出 的展开后的所有系数。为此，我们首先要做多项式乘法，对于计算机编程来说，并不困难。我们把一个关于 的多项式用一个整数数组 表示， 代表 的系数，然后卷积即可。
参考源码：
这样基于生成函数的方法实际上快了很多。
设第n个五边形数为 ，那么 ，即序列为：1, 5, 12, 22, 35, 51, 70, ...
对应图形如下：
设五边形数的生成函数为，那么有：
以上是五边形数的情况。下面是关于五边形数定理的内容：
五边形数定理是一个由欧拉发现的数学定理，描述欧拉函数展开式的特性。欧拉函数的展开式如下：
即：
可见，欧拉函数展开后，有些次方项被消去，只留下次方项为1, 2, 5, 7, 12, ...的项次，留下来的次方恰为广义五边形数。
五边形数和分割函数的关系：欧拉函数的倒数是分割函数的母函数，亦即：
其中 为 的分割函数。上式配合五边形数定理，有：
在 时，等式右侧的系数均为0，比较等式二侧的系数，可得
因此可得到分割函数的递归式：
所以，通过上面递归式，我们可以很快速地计算的整数划分方案数了。
参考代码：
以上设计的代码是最高效的。
通过比较上述四种算法，可见整数拆分的划分方法比较多样，且不同的算法运行效率差距比较大，需要仔细理解和思考。