数学上的整数拆分问题

逃离我推掉我的手 2022-11-09 12:54 242阅读 0赞

整数拆分是一个经典的数学问题，我们从小学奥数，一直到大学的组合数学，可能都会遇到。从字面意思来看，是将一个整数拆分成若干整数之和，求的是不同的方案个数。我今天想讨论的问题是 “ 无序拆分 ”，比如 3 = 2 + 1 或 1 + 2 看做同一种拆分方法。

数学家们在研究整数拆分这个问题上，其实花了很长的时间。那是一段怎样的历史呢？

无忧公主

注：为了方便表示，在此定义 p(n) 为将 n 拆分为若干正整数之和、顺序无关且允许重复的拆分方案个数。我们来计算一下 p(5)：5 可以拆分为 5、4+1、3+2、3+1+1、2+2+1、2+1+1+1、1+1+1+1+1，所以 p(5) = 7。

**1、欧拉**

18 世纪时，许多数学家都与欧拉保持着书信联系，一次，一位名叫诺地的先生问欧拉，是否研究过整数拆分问题。欧拉说，将 n 拆分为 m 个数的方案数，实际上就是：( 1 + x + x^2 + …… ) ( 1 + x^2 + x^4 + …… ) ( 1 + x^3 + x^6 + …… ) …… ( 1 + x^m + x^2m + …… ) 中 x^n 的系数。  
![在这里插入图片描述][20210315145416278.png]  
欧拉是什么意思呢？第一个括号，代表拆分出若干个 1；第二个括号，代表拆分出若干个 2……构成一个 x^n，需要每个括号中各一项相乘，其指数之和为 n，也就是一种拆分方案。而 x^n 的系数，相当于整数拆分的方案数了。

**其中的解法和上面提到的多项式乘法类似。**

欧拉的方法尽管巧妙，但凭借他的计算能力，也只能计算到 p(49) = 173525。毕竟在 1740 年时，是没有计算器或者计算机，人工手算的范围很有限。

其实欧拉的方法，后来被人称为 “ 母函数 ” 。

**2、拉马努金**

200 年过去了，这才出现了一位数学家，名叫拉马努金，计算出了 p(200) = 3972999029388。说到这里，我想介绍一下拉马努金，他从未接受过正规数学训练，但他具有惊人的数学直觉。他自己独立发现了近 3900 个数学公式和命题。  
![在这里插入图片描述][20210315145557720.png]  
他把自己所预见的数学命题全部记录在三大本笔记本上，但不写证明，只写命题。一位比利时数学家德利涅就是因为证明了拉马努金 1916 年提出的猜想，获得了菲尔兹奖。

不久以前有过一部讲述拉马努金一生的电影，其中也有提到过 “ 整数拆分 ” 哦。  
![在这里插入图片描述][20210315145614700.png]  
可见拉马努金是一位非常厉害的印度数学家。在计算整数拆分数时，他推出了计算整数拆分方案数的一个 “ 公式 ”（我暂且不知道怎么推的）：  
![在这里插入图片描述][20210315145642864.png]

下图是拉马努金的估算公式与实际 p(n) 之间的误差变化曲线图，当 n 越大时，误差其实就越小。其实我自己写了个程序验证的，之所以 n 只计算到 400，是因为再大一些的 p(n) 就要超过 64 位整数了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JyYXZlX2hlYXJ0NHB6ag_size_16_color_FFFFFF_t_70]  
当 n=400 时，误差约为 2.2%；我从网上的数据中得知，当 n=1000 时，误差缩小到 1.4% 左右。在计算机还没有出现的年代，拉马努金能推导出如此 “ 准确 ” 的公式，是非常不容易的！

[20210315145416278.png]: /images/20221023/1dc5c9d1e012403694a542cb604a144f.png
[20210315145557720.png]: /images/20221023/6eca1fe09d4f4dac8701c029dfd93071.png
[20210315145614700.png]: /images/20221023/8b6e9d43fe9548b8a6e8890d9950e32a.png
[20210315145642864.png]: /images/20221023/219e8bf54ac2427fa3e3357ae431c003.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JyYXZlX2hlYXJ0NHB6ag_size_16_color_FFFFFF_t_70]: /images/20221023/605831d9eb4f4fbea0181ee3dc3417e0.png