In high school or even middle school, we might encounter problems like this:
Let x, y, z be non-negative integers. How many different solutions are there for x + y + z = 2014? (Different orders are considered different solutions.)
A slightly more difficult version could be:
Let x, y, z be non-negative integers such that 0 \leq x \leq y \leq z. How many different solutions are there for x + y + z = 2014?
These problems belong to the category of integer partition problems (the widely known Goldbach’s conjecture is also an integer partition problem). There are many different approaches to solving these two problems; however, in my personal opinion, the most fascinating (and perhaps the most powerful) method is the "generating function method."
Regarding generating functions, this section will not provide an extensive introduction. If you lack the relevant background, please read related materials to understand this method. Many books on number theory, discrete mathematics, and computer science introduce the generating function method (also called the mother function method). Essentially, the generating function method has many applications because the property x^a \times x^b = x^{a+b} holds.
Ordered Partitions
We first solve the first problem, which is the number of ways to partition an integer n into the sum of k integers, where different orders are considered distinct partition methods. Let the number of ordered partitions of n be denoted as \alpha(n, k). It is not difficult 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 generating functions also lie in the fact that the Taylor expansions of functions such as \left(\frac{1}{1-x}\right)^k are 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 to say, the number of ways to partition n into k non-negative integers in an ordered manner is \alpha(n, k) = \binom{n+k-1}{k-1}. This is the same as the solution derived from permutations and combinations. The advantage of the generating function method is that the method itself is elegant; while the calculations may not always be simple, they can be carried out step-by-step. In fact, for problems that can be solved by other methods, the complexity does not increase if the generating function method is used instead.
In this problem, for n=2014 and k=3, the answer is \binom{2016}{2} = 2,031,120.
Unordered Partitions
The second problem belongs to unordered partitions, which is the number of ways to partition an integer n into the sum of k integers where different orders are considered the same partition method. Without using generating functions, one could obtain the answer through symmetry analysis or by enumerating and inducing from small numbers, but these methods involve many steps and make it difficult to obtain a general formula. Using generating functions is more direct. Let the number of unordered partitions of n be \beta(n, k). The generating function for this partition is slightly 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}
We will leave the derivation for the end and first look at what results this generating function brings us. Taking 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 to simplification is to transform the denominator into the form (1-x^p)^q, because the Taylor expansion of such a fraction is easy to find. Next, we calculate: \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 them 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 calculations show that the answer depends on the result of the partitioned number modulo 6. For example, \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. If the generating function method were not used, it would be difficult to derive a general expression.
In this problem, 2014 = 6 \times 335 + 4, so the answer is 4\binom{337}{2} + 2\binom{336}{2} = 339,024.
Unordered Partitions: Derivation
Why does the generating function for unordered partitions look like the one above? Let’s first consider the partition number for n = x + y where x \leq y. Clearly, according to the definition, it can correspond 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, it can be proved by induction that when partitioning into the sum of k non-negative integers, the generating function is: \prod_{r=1}^{k} \left(\frac{1}{1-x^r}\right) Interested readers can complete this process themselves; I believe you will gain much from it.
Updated on November 20, 2014:
Regarding unordered partitions, a more convenient derivation is as follows. For example, if n = x + y + z with x \leq y \leq z, let y = x + a and z = y + b = x + a + b. Then the natural number solutions for n = x + y + z with x \leq y \leq z are equivalent to the natural number solutions for n = 3x + 2a + b. Obviously, the generating functions for 3x, 2a, b are \frac{1}{1-x^3}, \frac{1}{1-x^2}, and \frac{1}{1-x} respectively. Multiplying them together gives the result.
When reprinting, please include the address of this article: https://kexue.fm/archives/2942
For more detailed reprinting matters, please refer to: Scientific Space FAQ