整数分拆(莱昂哈德·欧拉提出的理论)

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,比较等式二侧的系数,可得

整数分拆
参考代码:
以上设计的代码是最高效的。
通过比较上述四种算法,可见整数拆分的划分方法比较多样,且不同的算法运行效率差距比较大,需要仔细理解和思考。









































