整数分拆（莱昂哈德·欧拉提出的理论）
VLoG
次浏览
更新时间：2023-05-22
整数分拆
莱昂哈德·欧拉提出的理论
基本信息
| 中文名 | 整数分拆 |
| 外文名 | Integer splitting、Partition |
| 提出者 | 莱昂哈德·欧拉(Leonhard Euler) |
| 应用 | 研究各种分拆函数性质及相互关系 |
| 相关人物 | G.H.哈代 斯里尼瓦瑟·拉马努金 |
| 科目 | 数学 |
收起
原理
整数分拆问题是一个古老而又十分有趣的问题。所谓整数的分拆，指将一个正整数表示为若干个正整数的和。
分类
根据是否考虑分拆部分之间的排列顺序，我们可以将整数分拆问题分为有序分拆（composition）和无序分拆（partition）。两者之间的区别如下：
在有序分拆中，考虑分拆部分求和之间的顺序。假定
，
之间不同的排序记为不同的方案，称之为n的有序k拆分，如3的有序2拆分为：
。我们可以将这个问题建模为排列组合中的“隔板”问题，即n个无区别的球分为r份且每份至少有一个球，则需要用
个隔板插入到球之间的
个空隙，因此总共的方案数为
。
在无序拆分中，不考虑其求和的顺序。一般假定，
，我们称之为n的无序k拆分，如3的无序k拆分为：
。这种拆分可以理解为将n个无区别的球分为r份且每份至少有一个球。
一般情况下，无序拆分的个数用
表示，则
，
，
。
在通常情况下，整数分拆是指整数的无序分拆。
例子
例1 有1克、2克、3克、4克的砝码各一枚，问能称出多少重量，并各有几种称法。
该问题可以看成n拆分成1,2,3,4之和且不允许重复的拆分数，利用母函数计算如下：
例3 将15分拆成两个自然数的和，并使这两个自然数的积最大，如何分拆？
分析与解 不考虑加数顺序，可将15分拆成下列形式的两个自然数的和：
。显见，将15分拆成
时，有最大积
。
注：从上述两例可见，将一个自然数分拆成两个自然数的和时，如果这个自然数是偶数2m，当分拆成
时，有最大积
；如果这个自然数是奇数
，当分拆成
时，有最大积
。
例4 将14分拆成3个自然数的和，并使这三个自然数的积最大，如何分拆？
分析与解 显然，只有使分拆成的数之间的差尽可能地小（比如是0或1），这样得到的积才最大。这样不难想到将14分拆成
时，有最大积
。
拆分数估计
拆分数估计定理证明
拆分数性质
性质一
整数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到
这 个数字的组合，每个数字理论上可以无限重复出现，即个数随意，使它们的和为。显然，数字
可以有如下可能，出现0次（即不出现），1次，2次，…，
次等等。把数字用 
表示，出现 次的数字用 
表示，不出现用1表示。例如，数字2用 
表示，2个2用 
表示，3个2用 
表示，k个2用 
表示。则对于从1到 的所有可能组合结果我们可以表示为：
上面的表达式中，每个括号内的多项式代表了数字的参与到划分中的所有可能情况。因此，该多项式展开后，由于
，因此 就代表了 的划分，展开后项的系数也就是的所有划分个数，即
。
由此我们找到了关于整数划分的母函数，剩下的问题就是，我们需要求出 的展开后的所有系数。为此，我们首先要做多项式乘法，对于计算机编程来说，并不困难。我们把一个关于
的多项式用一个整数数组
表示，
代表 的系数，然后卷积即可。
参考源码：
这样基于生成函数的方法实际上快了很多。
五边形数法
对应图形如下：
整数分拆
其中 为 的分割函数。上式配合五边形数定理，有：
在 时，等式右侧的系数均为0，比较等式二侧的系数，可得
整数分拆
参考代码：
以上设计的代码是最高效的。
通过比较上述四种算法，可见整数拆分的划分方法比较多样，且不同的算法运行效率差距比较大，需要仔细理解和思考。
