Generating Functions and the Partitioning of Integers

生成函数法与整数的分拆 苏剑林 · 2014-09-16 · Mathematics generating function generating function partition combinatorics

In high school, or even middle school, we may well have encountered a problem like this:

Let $x,y,z$ be non-negative integers. How many distinct solutions does $x+y+z=2014$ have? (Different orderings count as different solutions.)

A slightly harder version might be:

Let $x,y,z$ be non-negative integers with $0\leq x\leq y\leq z$. How many distinct solutions does $x+y+z=2014$ have?

Both of these are problems of partitioning integers (the well-known Goldbach conjecture is itself an integer-partitioning problem). There are many different ways to solve these two problems, but personally I find that the most captivating — and perhaps also the most powerful — of them is the "generating function method."

I won't spend much time introducing generating functions here; readers who lack the relevant background should first consult other material to get familiar with the method. Many books on number theory, discrete mathematics, and computer science cover the generating function method (also called the method of generating series). At its core, the reason the generating function method has so many applications is the fact that the identity $x^a\times x^b=x^{a+b}$ holds. more

Ordered partitions

Let's first tackle the first problem: partitioning the integer $n$ into an ordered sum of $k$ integers, where different orderings are counted as different partitions. Denote the number of ordered partitions of $n$ by $\alpha(n,k)$. It's easy to derive:

$$\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}$$

The effectiveness and convenience of the generating function method also come from the fact that the Taylor expansion of a function like $\left(\frac{1}{1-x}\right)^k$ is easy to obtain:

$$\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}$$

That is, the number of ordered partitions of $n$ into a sum of $k$ positive integers is $\alpha(n,k)=\binom{n+k-1}{k-1}$. This agrees with the result obtained via combinatorics. The beauty of the generating function method lies in the elegance of the approach itself — the computations may not be trivial, but they can always be carried out step by step in a systematic way. In fact, for problems that can be solved by other methods, switching to the generating function method does not increase the complexity.

For this problem, taking $n=2014$, the answer is $\binom{2016}{2}=2031120$.

Unordered partitions

The second problem concerns unordered partitions — that is, partitioning the integer $n$ into a sum of $k$ integers, where different orderings are regarded as the same partition. Without the generating function method, one could work out the answer step by step through symmetry arguments, or by enumerating small cases and generalizing inductively, but both approaches involve many steps and make it hard to obtain a general formula. The generating function method is far more direct here. Denote the number of unordered partitions of $n$ by $\beta(n,k)$; the generating function for this partition is somewhat more complex:

$$\begin{aligned}\sum_{n=0}^{\infty}\beta(n,k)x^n&=\prod_{r=1}^{k}\left(\frac{1}{1-x^r}\right)\end{aligned}$$

Let's postpone the derivation to the end and first see what results this generating function gives us. Take $k=3$ as an example:

$$\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}$$

The key trick in simplifying is to put the denominator into the form $(1-x^p)^q$, since the Taylor expansion of a fraction in this form is easy to compute. We then obtain:

$$\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.$$

Multiplying these together gives:

$$\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}$$

The above calculation shows that the answer depends on the residue of the number being partitioned modulo 6; for instance, $\beta(6n,3) = \binom{n+2}{2} + \binom{n}{2} + 4\binom{n+1}{2}$ while $\beta(6n+1,3)=\binom{n+2}{2}+5\binom{n+1}{2}$, and so on. Without the generating function method, it would be difficult to obtain such a general expression.

For this problem, $2014=6\times 335+4$, so the answer is $4\binom{337}{2}+2\binom{336}{2}=339024$.

Unordered partitions: derivation

Why does the generating function for unordered partitions take the form given above? Let's first consider the number of partitions of $n=x+y,x\leq y$. By definition, it clearly corresponds to the generating function:

$$\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}$$

More generally, one can prove by induction that when partitioning into a sum of $k$ positive integers, the generating function is

$$\prod_{r=1}^{k}\left(\frac{1}{1-x^r}\right)$$

Interested readers are encouraged to work through this derivation themselves — I believe it will be quite rewarding.

Update, November 20, 2014:

Here is a more convenient way to derive the case of unordered partitions. For example, take $n=x+y+z, x\leq y\leq z$, and set $y=x+a,z=y+b=x+a+b$. Then the natural-number solutions of $n=x+y+z, x\leq y\leq z$ correspond exactly to the natural-number solutions of $n=3x+2a+b$. Clearly the generating functions of $3x,2a,b$ are $\frac{1}{1-x^3}$, $\frac{1}{1-x^2}$, and $\frac{1}{1-x}$ respectively, and multiplying them together gives the result.