生成函数法与整数的分拆
By 苏剑林 | 2014-09-16 | 31371位读者 |我们在高中甚至初中,都有可能遇到这样的题目:
设$x,y,z$是非负整数,问$x+y+z=2014$有多少组不同的解?(不同顺序视为不同的解)
难度稍高点,可以改为
设$x,y,z$是非负整数,$0\leq x\leq y\leq z$,问$x+y+z=2014$有多少组不同的解?
这些问题都属于整数的分拆问题(广为流传的哥德巴赫猜想也是一个整数分拆问题)。有很多不同的思路可以求解这两道题,然而,个人认为这些方法中最引人入胜的(可能也是最有力的)首推“生成函数法”。
关于生成函数,本节就不多作介绍了,如果缺乏相关基础的朋友,请先阅读相关资料了解该方法。不少数论的、离散数学的、计算机科学的书籍中,都介绍了生成函数法(也叫母函数法)。本质上讲,母函数法能有诸多应用,是因为$x^a\times x^b=x^{a+b}$这一性质的成立。
有序的分拆
我们首先来解决第一个问题,也就是把整数$n$分拆为$k$个整数和的拆分数,不同的顺序也视为不同的分拆方式。记$n$的有序分拆数记为$\alpha(n,k)$,不难推出
$$\begin{aligned}\sum_{n=0}^{\infty}\alpha(n,k)x^n&=\left(1+x+x^2+x^3+x^4+\dots\right)^k\\
&=\left(\frac{1}{1-x}\right)^k\end{aligned}$$
生成函数的有效性和便捷性还在于诸如$\left(\frac{1}{1-x}\right)^k$这一类函数的泰勒展开式是很容易求得的:
$$\begin{aligned}\left(\frac{1}{1-x}\right)^k&=\frac{1}{(k-1)!}\left(\frac{1}{1-x}\right)^{(k-1)}\\
&=\frac{1}{(k-1)!}\left(1+x+x^2+x^3+x^4+\dots\right)^{(k-1)}\\
&=\frac{1}{(k-1)!}\sum_{n=k-1}^{\infty}\frac{n !}{(n-k+1)!}x^{n-k+1}\\
&=\sum_{n=0}^{\infty}\binom{n+k-1}{k-1}x^{n}
\end{aligned}$$
也就是说,将$n$进行有序分拆为$k$个正整数之和的分拆数$\alpha(n,k)=\binom{n+k-1}{k-1}$。这跟从排列组合出发的解法是一样的。生成函数法的优点在于,方法本身是很美妙的,而计算未必简单,但都是可以按部就班计算下去的。事实上,用其他方法能够解决的问题,如果改用生成函数法,复杂程度并不会增加。
在本题中,对于$n=2014$,给出答案为$\binom{2016}{2}=2031120$。
无序的分拆
第二个问题属于无序地分拆,也就是把整数$n$分拆为$k$个整数和的拆分数,不同的顺序也视为同一种分拆方式。如果不用生成函数法,则可以通过对称性的分析逐步求得答案,也可以通过小的数字逐步枚举归纳,但都是步骤较多,而且难以得到一般的公式。用生成函数法则显得更为直接。记$n$的无序分拆数为$\beta(n,k)$,关于该分拆的生成函数稍微复杂一些:
$$\begin{aligned}\sum_{n=0}^{\infty}\beta(n,k)x^n&=\prod_{r=1}^{k}\left(\frac{1}{1-x^r}\right)\end{aligned}$$
我们把推导放到最后,首先来看这样的生成函数给我们带来什么样的结果。这里就$k=3$为例:
$$\begin{aligned}
&\left(\frac{1}{1-x}\right)\left(\frac{1}{1-x^2}\right)\left(\frac{1}{1-x^3}\right)\\
=&\frac{1+x}{(1-x^2)^2 (1-x^3)}\\
=&\frac{(1+x)(1+x^2+x^4)^2}{(1-x^6)^2 (1-x^3)}\\
=&\frac{(1+x)(1+x^2+x^4)^2 (1+x^3)}{(1-x^6)^2 (1-x^6)}\\
=&\frac{(1+x)(1+x^2+x^4)^2 (1+x^3)}{(1-x^6)^3}
\end{aligned}$$
化简的要诀在于将分母变成$(1-x^p)^q$的形式,因为这样形式的分式的泰勒展式是容易求出来的。下面,我们算得:
$$\left\{\begin{aligned}&(1+x)(1+x^2+x^4)^2 (1+x^3)=1 + x + 2 x^2 + 3 x^3 + 4 x^4 + 5 x^5 \\
&\qquad\qquad\qquad\qquad\qquad\qquad+ 4 x^6 + 5 x^7 + 4 x^8 + 3 x^9 + 2 x^{10} + x^{11} + x^{12}\\
&\frac{1}{(1-x^6)^3}=\sum_{n=0}^{\infty}\binom{n+2}{2}x^{6n}
\end{aligned}\right.$$
相乘得
$$\begin{aligned}
&\sum_{n=0}^{\infty}\left[\binom{n+2}{2}+\binom{n}{2}+4\binom{n+1}{2}\right]x^{6n}\\
+&\sum_{n=0}^{\infty}\left[\binom{n+2}{2}+5\binom{n+1}{2}\right]x^{6n+1}\\
+&\sum_{n=0}^{\infty}\left[2\binom{n+2}{2}+4\binom{n+1}{2}\right]x^{6n+2}\\
+&\sum_{n=0}^{\infty}\left[3\binom{n+2}{2}+3\binom{n+1}{2}\right]x^{6n+3}\\
+&\sum_{n=0}^{\infty}\left[4\binom{n+2}{2}+2\binom{n+1}{2}\right]x^{6n+4}\\
+&\sum_{n=0}^{\infty}\left[5\binom{n+2}{2}+\binom{n+1}{2}\right]x^{6n+5}\\
\end{aligned}$$
以上的计算表明,答案跟被分拆数模6的结果有关,比如$\beta(6n,3) = \binom{n+2}{2} + \binom{n}{2} + 4\binom{n+1}{2}$而$\beta(6n+1,3)=\binom{n+2}{2}+5\binom{n+1}{2}$,等等。倘若不通过生成函数法,则难以求得一般表达式出来。
在本题中,$2014=6\times 335+4$,所以给出答案$4\binom{337}{2}+2\binom{336}{2}=339024$。
无序的分拆:推导
为什么无序分拆的生成函数会是上述的样子?我们先考虑$n=x+y,x\leq y$的分拆数,显然,根据定义,它可以对应于生成函数:
$$\begin{aligned}&1\times(1+x+x^2+x^3+\dots)+x\times(x+x^2+x^3+x^4+\dots)\\
&+x^2\times(x^2+x^3+x^4+x^5\dots)+x^3\times(x^3+x^4+x^5+x^6\dots)+\dots\\
=&\frac{1}{1-x}+\frac{x^2}{1-x}+\frac{x^4}{1-x}+\frac{x^6}{1-x}+\dots\\
=&\frac{1}{(1-x)(1-x^2)}\end{aligned}$$
更一般地,可以归纳地证明,分拆为$k$个正整数之和时,其生成函数是
$$\prod_{r=1}^{k}\left(\frac{1}{1-x^r}\right)$$
有兴趣的朋友可以亲自动手完成这一过程,相信会收获不少。
2014年11月20日更新:
关于无序的分拆,更方便的一个推导是这样的。比如说$n=x+y+z, x\leq y\leq z$,那么设$y=x+a,z=y+b=x+a+b$,那么$n=x+y+z, x\leq y\leq z$的自然数解,就相当于$n=3x+2a+b$的自然数解,显然$3x,2a,b$的生成函数分别是$\frac{1}{1-x^3}$、$\frac{1}{1-x^2}$和$\frac{1}{1-x}$,相乘起来即可。
转载到请包括本文地址:https://spaces.ac.cn/archives/2942
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Sep. 16, 2014). 《生成函数法与整数的分拆 》[Blog post]. Retrieved from https://spaces.ac.cn/archives/2942
@online{kexuefm-2942,
title={生成函数法与整数的分拆},
author={苏剑林},
year={2014},
month={Sep},
url={\url{https://spaces.ac.cn/archives/2942}},
}
July 21st, 2015
感觉站主的研究怪怪的,站主这是9月的帖,分类标签有组合数学,而这也正是组数,可10月的帖暗含站主不组数一研究分拆整数的内容,奇哉