Mathematics
An Introduction to Integer Partitions
Stairway to H̶e̶a̶v̶e̶n̶
A typical stairway is made up of thirteen to sixteen stairs. For our purpose in this introduction, let’s consider a modest stairway made up of just 5 stairs. We want to determine how many different ways there are to climb the stairs. Let’s find out:
- The usual or common way is to climb one(1) stair at a time untill we get to the top, let’s represent this strategy by 1 +1 + 1 + 1 + 1.
- Another way would be to climb two stairs at a time first, then climb the remaining three stairs one by one. Let’s save this as 2 + 1 + 1 + 1.
- Yet another way is to leap over two stairs at a go, then another two stairs at a go, then the last one stair, that is 2 + 2 + 1.
- A fourth strategy is to climb three stairs at a go, then the remaining two stairs one by one, that is 3 + 1 + 1.
- Yet another strategy is: climb three stairs at a go, then climb the remaining two stairs at a go too, that is 3 + 2.
- The sixth strategy is: climb four stairs at a go, then climb one stair. That is 4 + 1.
- If you are feeling like an olympic champion you could take just one giant leap, scaling all the 5 stairs at once! Bravo. Strategy seven = 5.
So, are these all the possible ways of ascending the stairway in question? Not quite, another option not listed above is: climb one stair first then climb the remaining four stairs at one go(1 + 4). But this is just option 6 in reverse. They contain the same set of numbers, 1 and 4.
If the order of arrangement of the numbers does not matter then there are just 7 ways of climbing a 5-stairs stairway. We say the number of partitions of 5 is 7. Each climbing strategy represents a partition of the number of stairs.
Formal Definition, Basic Concepts
A partition of a positive integer n is a sequence of positive integers that sum up to n. From the introduction, the partitions of 5 are 1 +1 + 1 + 1 + 1, 2 + 1 + 1 + 1, 2 + 2 + 1, 3 + 1 + 1, 3 + 2, 4 + 1, and 5. Seven in total.
Each summand in a partition is called a part(as you would expect), and the order of arrangement of parts is immaterial, 2 + 2 + 1 is the same partition as 1 + 2 + 2, and 2 + 1 + 2. When order matters, the sequence is called a composition.
p(n) is used to denote the partition function, which gives the number of unrestricted partitions of n, e.g. p(5) = 7. When we impose some sort of restriction on the parts, we have restricted partitions. Usual restrictions include restricting the parts to only odd numbers, restricting to distinct parts, limiting the number of parts, limiting the sizes of the parts, etc.
Example : Let p(n, k) denote the number of partitions of n with exactly k parts, then p(5, 2) = 2 (counting just 4 + 1, and 3 + 2).
It’s obvious that for all n, p(n, n) = p(n, 1) = 1, isn’t it?
The values of p(n) for n = 0 to 9 are shown in the table below.
Note that p(0) has a value of 1, we’ll come back to that later.
Exercise: Work out the values of p(10), p(10, 5), p(10, 6).
Finding a Formula for p(n)
Finding the value of p(n) by listing out all the partitions of n and counting them can be a tricky business, even for moderate values of n. An algebraic formula would be very nice to have.
Sadly, there is no known natural formula for p(n). By natural we mean a formula that is direct, combinatorial (discrete) and exact all at once. Nevertheless, there are some indirect methods and sophisticated formulas for computing p(n). We’ll look at some of them.
Euler’s Generating Function
We begin with a simple but super-clever insight by Leonhad Euler, the legendary Swiss mathematician, who did much of the pioneering work in this field.
Euler observed that when we multiply out a set of infinite polynomials of the form: (1 + x + x² + x³ + x⁴ + …)(1 + x² + x⁴ + x⁶ + …)(1 + x³ + x⁶ + x⁹ + …)…, the coefficient of xⁿ in the resulting product gives the partition number of n, that is, p(n). We’ll give an handwavy explanation of why this is true:
Let G(x) = (1 + x + x² + x³ + x⁴ + …)(1 + x² + x⁴ + x⁶ + …)(1 + x³ + x⁶ + x⁹ + …)…(1 + xⁿ + x²ⁿ + x³ⁿ + …)…
On expansion, G(x) takes the following shape:
1 + c₁x + c₂x² + c₃x³ + c₄x⁴ + …+ cₙxⁿ + …
The general term cₙxⁿ in the expansion comes about as a result of multiplying terms whose exponents sum up to n, then adding the products. For example, to get c₃x³, all the possible configurations are:
Configuration 1: Multiply x(that is x¹) from the first bracket with x² from the second bracket. Sum of exponents is 1 + 2 = 3.
Configuration 2: Take x³ from the first bracket( and multiply with 1 from all other brackets).
Configuration 3: Take x³ from the third bracket( and multiply with 1 from all other brackets).
Next, add up the x³’s to get 3x³. So, c₃ = 3, which is the value of p(3).
Generally, the coefficient, cₙ, of xⁿ in the expansion of G(x) gives the value of p(n) because each configuration(as defined above) actually represents a unique partition of n(since the exponents sum up to n and in different ways). And when we add up the xⁿ’s to get cₙxⁿ, it’s obvious that cₙ is a count of the number of partitions of n. QED.
G(x) is called the generating function for p(n). Each of it’s constituent polynomial is an infinite geometric progression with general form
1 + xᵏ + x²ᵏ + x³ᵏ + x⁴ᵏ +…(First term = 1, common ratio = xᵏ).
Using the formula for the sum of an infinite geometric progression and the shorthand notations for sum and product, we can write:
There you have the partition function implicitly defined by the generating function. If there was a way to wring it out and make it the subject of the formula.
Now, let’s apply this method to find p(4). We want to find the coefficient of x⁴ in the expansion of G(x). Fortunately, we don’t need to multiply out the whole infinite set of polynomials; since terms with exponents higher than 4 don’t contribute to the coefficient of x⁴, we can truncate them in each bracket.
We just need to multiply out the following:
(1 + x + x² + x³ + x⁴ )(1 + x² + x⁴ )(1 + x³)(1 + x⁴)
You should work it out by hand, but using an online polynomial multiplication program, we obtain:
1 + x + 2x² + 3x³ + 5x⁴ + 5x⁵ + 6x⁶ + 7x⁷ + 7x⁸ + 6x⁹ + 5x¹⁰ + 5x¹¹ + 3x¹² + 2x¹³ + x¹⁴ + x¹⁵
From this, we get that p(4) = 5. Note that the result also yields the values of p(3), p(2), p(1), and p(0). See now why p(0) = 1?
The coefficients of x with exponents higher than n=4 are not guaranteed to represent p(n) because of the truncation we did, but generally, the expansion yields correct values of p(n) for all integers less than n as well. Talk about asking for a tree and getting the forest(or at least a part of it).
So, we have transformed the problem of counting partitions to the problem of multiplying polynomials, which is amenable to algorithmization. Thanks to the idea of a generating function.
A Recurrence Formula
Euler pentagonal number theorem. Euler discovered the following identity:
The exponents of x on the right hand side(1, 2, 5, 7, 12, …) are numbers of the form k(3k − 1)/2 (where k = 0, 1, −1, 2, −2, 3, −3, 4…), called the generalized pentagonal numbers, hence the identity is known as the pentagonal number theorem. Using the pi and sigma notations, the identity can be succinctly stated as:
We can combine this theorem with the the generating function for p(n) stated earlier to derive a recursive formula for p(n) as follows:
The numbers in the brackets are once again the pentagonal numbers, of form k(3k − 1)/2, and the sign before each term is the sign of -1 rasised to the power of |k| + 1, where |k| is the absolute value of k. With that you can continue the recurrence formula for as long as needed.
Notice how the tree-and-forest situation shows up again, this time in reverse - to get a tree, give the forest(or at least a part of it).
To calculate p(9) for example, we’ll need to know p(8), p(7), etc. If those values are not already pre-computed, we may just start with p(0) = 1 and work upwards.
p(9) = p(8) + p(7) - p(4) - p(2) + p(-3) + p(-6) - …
p(n) = 0 for negative values of n.
So, we are left with p(9) = p(8) + p(7) - p(4) - p(2).
Direct Formulas
In 1918, G. H. Hardy and S. Ramanujan came up with the following approximate formula for p(n):
It is an asymptotic formula, the approximation gets closer and closer to the real value of p(n) as n gets bigger and bigger, the formula itself is an approximation(the first term) of the following asymptotic series:
Where Aₖ(n) is some complex function of n.
Another mathematician, Hans Rademacher, in 1937, improved upon the formula to produce:
In fact, this formula is as good as being exact, when rounded up to the nearest integer, it gives the exact value of p(n).
Ramanujan, Hardy, Rademacher. How on earth did they come up with such humongous formulas? Basically by trying to wring out p(n) out of the generating function. It’s no mean feat, it involves some deep and ingenious analytic techniques.
Visualizing Partitions
Partitions can be visually represented by Young diagrams, which consist of rows of cells, with the number of cells in a row corresponding to the size of a part.
For example the partition 7 + 4 + 2 + 1 has the following Young diagram:
The diagram is read row-wise, if we rotate it about the diagonal or just read it column-wise, we get the conjugate of the partition, so the conjugate of the above partition(7 + 4 + 2 + 1) would be 4 + 3 + 2 + 2 + 1 + 1 + 1. Note that the number of parts in the conjugate partition equals the size of the largest part in the original partition, this observation holds generally.
When a partition is the same as its conjugate, the partition is said to be self-conjugate. Exercise: Verify that 5 + 4 + 2 + 2 + 1 is self-conjugate.
Young diagrams are useful for easily(visually) deducing or proving theorems about partitions. The following theorem, for instance, is based on the observation that the number of parts in a conjugate partition equals the size of the largest part in the original partition.
Theorem: The number of partitions of n into k parts is equal to the number of partitions of n with k as the largest part.
Ramanujan’s Congruences
By observing a large table of values of p(n), Ramanujan made some remarkable observations about the divisibility properties of the partition function:
(i). p(n) leaves a remainder of 0 when divided by 5 whenever n is a number like 4, 9, 14, 19, etc. In other words, p(n) is a multiple of 5 when n is of the form 5k + 4. For example p(9) = 30, a multiple of 5.
(ii). p(n) is a multiple of 7 when n is a number of the form 7k + 5. Example: p(26) = 2436, a multiple of 7.
(iii). p(n) is a multiple of 11 when n is a number of the form 11k + 6. Example: p(17) = 297, a multiple of 11.
These observations can be written in the language of congruences (modular arithmetic) as follows:
(i). p(5k + 4) ≡ 0 (mod 5)
(ii). p(7k + 5) ≡ 0 (mod 7)
(iii). p(11k + 6) ≡ 0 (mod 11)
Note that the divisors are prime numbers. Following the pattern, it is tempting to think that the next congruence should be something like
p(13k + c) ≡ 0 (mod 13), but there is no such congruence.
Research about partition congruences continues still.
Activities and Challenges
- Assuming order matters , that is, 2 + 3 is not the same as 3 + 2, workout the total number of ways there are to climb the 5-stair stairway in the introduction.
- Find the conjugate of the following partition of 20; 8 + 7 + 3 + 2.
- What are the self-conjugate partitions of 5? How many are they?
- (i) Write a program in your favorite language to find p(n) using the method of polynomial expansion.
(ii) Write a program in your favorite language to find p(n) using the recurrence formula.
(iii) Compare the execution times of the two programs for the following values of n: 10, 20, 30, 50, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000. - Write a program in your favorite language to find the conjugate of a partition.
