Power Series and Generating Functions (III) – Partitions

One particularly fruitful application of generating functions is in partition numbers.

Let n be a positive integer. A partition of n is an expression of n as a sum of positive integers, where two expressions are identical if they can be obtained from each other via a permutation. For example, 7 = 3 + 2 + 1 + 1 and 7 = 3 + 1 + 1 + 2 are identical partitions. Or one can also write a partition as an expression $n = a_1 + a_2 + \dots + a_k$ , where $a_1 \ge a_2 \ge \dots \ge a_k$ are positive integers. We are interested in counting the number of partitions of n, which is denoted by p(n).

Example: p(5) = 7 since we can write

5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1

The partition numbers were a pet favourite of the late Ramanujan who found various congruence relations involving partition numbers and even a rapidly converging formula which he later used to compute p(100) and p(200) exactly (the latter had 13 digits, and those were the days without electronic computation tools!).

One effective way of representing a partition is by means of a Young diagram. Corresponding to the partition $n = a_1 + a_2 + \dots + a_k$ , where $a_1 \ge a_2 \ge a_3 \ge \dots$ , we place $a_1$ dots on a row, evenly spaced apart and starting from a left margin; then $a_2$ dots on the second row, again evenly spaced apart and starting from the same left margin, etc. For example, for the two partitions 18 = 6+5+3+3+1 = 4+4+4+3+1+1+1, we have the corresponding Young diagrams.

Problem 1. Prove that the number of partitions of n into k parts is equal to the number of partitions of n into parts, the largest of which is k. E.g. if n = 7, k = 3, then we have:

7 = 5+1+1 = 4+2+1 = 3+3+1 = 3+2+2, (exactly 3 parts)

7 = 3+3+1 = 3+2+2 = 3+2+1+1 = 3+1+1+1+1, (the largest part is 3).

Sketch of Proof. Construct a bijection between the two sets of partitions, by taking the transpose (i.e. reflection about the main diagonal line). This is also called the conjugate. The following diagram shows an example.

What is truly of interest to us here is the generating function for the partition numbers $f(x) = p(0) + p(1)x + p(2)x^2 + \dots$ , where p(0) is taken to be 1 (there’s just one way to partition 0: i.e. don’t do anything). Now, instead of looking at the individual parts in a partition, we can count the number of 1’s, the number of 2’s etc and represent this by a tuple $(r_1, r_2, \dots)$ of non-negative integers such that $\sum_i (ir_i) = n$ . For example, the above two Young diagrams correspond to tuples (1, 0, 2, 0, 1, 1) and (3, 0, 1, 3) respectively. This gives:

$f(x) = (1 + x + x^2 + x^3 + \dots)(1 + x^2 + x^4 + \dots)(1 + x^3 + x^6 + \dots)\dots = \prod_{m=1}^\infty \frac 1 {1 - x^m}$ .

Problem 2. Let q(n) be the number of partitions of n into parts which are greater than 1. Prove that q(n) = p(n) – p(n-1).

Proof. From the above reasoning, we see that the generating function for q(n), i.e. the power series $f(x) = q(0) + q(1)x + q(2)x^2 + \dots$ is given by:

$(1 + x^2 + x^4 + \dots)(1 + x^3 + x^6 + \dots)(1 + x^4 + x^8 + \dots)\dots = \prod_{m=2}^\infty \frac 1 {1 - x^m}$ .

This shows that if g(x) is the generating function for p(n) then $g(x) = (1-x)^{-1} f(x)$ or $f(x) = (1-x)g(x)$ . Comparing the coefficient of $x^n$ on both sides then gives q(n) = p(n) – p(n-1). ♦

Problem 3. Prove that the number of partitions of n into disjoint parts is equal to the number of partitions of n into odd parts. E.g. for n = 6, we have:

6, 5+1, 4+2, 3+2+1 and 5+1, 3+3, 3+1+1+1, 1+1+1+1+1+1.

Proof. Consider the generating function for q(n), the number of partitions of n into odd parts. The corresponding generating function $q(0) + q(1)x + q(2)x^2 + \dots$ for the sequence is

$\left(\sum_{i=0}^\infty x^i\right)\left(\sum_{i=0}^\infty x^{3i}\right)\left(\sum_{i=0}^\infty x^{5i}\right) \dots = \frac 1 {(1-x)(1-x^3)(1-x^5)(1-x^7)\dots}$ .

Multiplying the numerator and the denominator by the “missing even terms” $(1-x^2)(1-x^4)(1-x^6)\dots$ we get:

$\frac{(1-x^2)(1-x^4)(1-x^6)\dots}{(1-x)(1-x^2)(1-x^3)\dots} = \frac{1-x^2}{1-x} \cdot\frac{1-x^4}{1-x^2}\cdot \frac{1-x^6}{1-x^3}\cdots = (1+x)(1+x^2)(1+x^3)\dots$

and we see that the final power series is the generating function for the number of partitions of n into distinct parts. ♦

Problem 4. (AMM 11464) Let a(n) be the number of ways to place n identical balls into urns $U_1, U_2, \dots$ such that (i) $U_1$ gets at least one ball, and (ii) while any balls remain, each successive urn receives at least as many balls as all previous urns combined. On the other hand, let b(n) be the number of partitions of n into powers of 2, possibly with repeated terms. Prove that a(n) = b(n). E.g. if n = 6, then:

a(6) : 114, 123, 15, 24, 33, 6, b(6) : 111111, 11112, 1122, 114, 222, 24.

Proof. Let $g(x) = b(0) + b(1)x + b(2)x^2 +\dots$ be the generating function of the sequence b(n). From the above argument, it’s clear that:

$g(x) = (1-x)^{-1}(1-x^2)^{-1} (1-x^4)^{-1}\dots = \prod_{i=0}^\infty \left(1 - x^{2^i}\right)^{-1}.$

Thus, algebra gives us

$g(x^2) = (1-x^2)^{-1}(1-x^4)^{-1}(1-x^8)^{-1}\dots = (1-x)g(x)$ .

Comparing the coefficients of $x^m$ on both sides then gives us:

$b(2n+1) = b(2n)$ ;
$b(2n) = b(2n-1) + b(n)$ .

We claim that the sequence a(n) satisfies the same two recurrence relations. The result would then follow from a(1) = b(1) = 1. To show that $a(2n+1) = a(2n)$ , suppose we distribute 2n+1 balls among the urns. Look at the last urn: the number of balls in this urn must be more than the number of balls in all prior urns; for if it were equal, then the total number of balls would be even (contradiction). By removing 1 ball from the last urn, we get a bijection between the distributions of 2n+1 balls and those of 2n balls.

To prove $a(2n) = a(2n-1) + a(n)$ , consider a distribution of 2n balls. If the last urn has as many balls as all prior urns combined, then removing the last urn gives us a distribution of n balls. If it has more, then removing one ball gives a distribution of 2n-1 balls. You can easily check that we obtain bijections in both cases. This completes the proof. ♦

Exercises.

Let m, n be positive integers with $n > \frac 1 2 m(m+1)$ . Prove that the number of partitions of n into m distinct parts is equal to the number of partitions of $n - \frac 1 2 m(m+1)$ into at most m parts.
Solve Problem 2 via a combinatorial argument.
Prove that the number of partitions of n in which no integer occurs more than k-1 times, equals the number of partitions of n into parts which are not divisible by k.
A partition is said to be self-conjugate if its Young diagram is identical to its conjugate (or transpose). Prove that the number of self-conjugate partitions of n is equal to the number of partitions of n into distinct odd parts.
Find a closed form for the number of partitions of n into 1, 2 and 3, i.e. find the number of ways to obtain $n if we have only $1, $2 and $3 notes. [ We’ll give the answer here: $\frac 1 8 (-1)^n + \frac{47}{72} + \frac n 2 + \frac {n^2} {12} + \frac 1 9 (\omega^n + \omega^{2n})$ , where $\omega = \frac{-1+\sqrt{-3}}2$ is a 3rd root of unity, satisfying $\omega^2 + \omega + 1 = 0$ . If you’re not familiar with complex numbers, just note that $\omega^n + \omega^{2n}$ is 2 (resp. -1) if n is divisible (resp. not divisble) by 3. ]
Let c(n) be the number of partitions $n = a+b+c+d$ where $a\ge 0$ , $b\ge 2a$ , $c \ge 2b$ , $d \ge 2c$ . Prove that the generating function of c(n) is $(1-x)^{-1}(1-x^3)^{-1}(1-x^7)^{-1}(1-x^{15})^{-1}$ .
Let c(n) be the number of partitions of n into k parts, each of which is at most l. Prove that the generating function of c(n) is given by: $\frac{(1-x)(1-x^2)\dots(1-x^{k+l})}{(1-x)(1-x^2)\dots(1-x^k)\times(1-x)(1-x^2)\dots(1-x^l)}$ .

Extra Stuff. What’s a good way of computing p(n)? There doesn’t seem to be a closed form although there are asymptotic expressions which converge rather fast. One rather practical way of obtaining p(n) for modestly large values of n is via a recurrence relation.

Pentagonal Number Theorem. The power series $(1-x)(1-x^2)(1-x^3)\dots = \prod_{i=1}^\infty (1-x^i)$ , when expanded, has very few non-zero entries. To be specific:

$\prod_{i=1}^\infty (1-x^i) = \sum_{k=-\infty}^\infty (-1)^k x^{k(3k-1)/2}.$

The first few terms are $1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \dots$ .

Since this power series is precisely the inverse of the power series f of p(n), we thus get:

$f(x)(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \dots) = 1$ .

Taking the coefficient of xⁿ for n > 0, we get

$p(n) - p(n-1) - p(n-2) + p(n-5) + p(n-7) - p(n-12) - p(n-15) + \dots = 0,$

which is rather efficient since we only need to worry about $\sqrt{n/3}$ terms above. If you know programming, you can now use Python to calculate up to p(1000) easily. 🙂

Power Series and Generating Functions (III) – Partitions

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages

Power Series and Generating Functions (III) – Partitions

Share this:

Like this:

Related

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Pages