Partitions and Pentagons

This post will present a remarkable theorem of Euler which makes a connection between integer partitions and pentagons.

Partitions

A partition of an integer n is a way of writing n as a sum of positive integers. For example, there are seven unordered partitions of 5:

• 5
• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

Note that order does not matter. For instance, 4 + 1 and 1 + 4 count as the same partition. You can get a list of partitions of n in Mathematica with the function IntegerPartitions[n]. If we enter IntegerPartitions[5] we get

 {{5}, {4, 1}, {3, 2}, {3, 1, 1}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}}

We say a partition is distinct if all the numbers in the sum are distinct. For example, these partitions of 5 are distinct

• 5
• 4 + 1
• 3 + 2

but these are not

• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

because 1 appears more than once in each sum.

We can divide distinct partitions into those having an even number of terms and those having an odd number of terms. In the example above, there is one odd partition, just 5, and two even partitions: 4 + 1 and 3 + 2.

Pentagonal numbers

The pentagonal numbers are defined by counting the number of dots in a graph of concentric pentagons: 1, 5, 12, 22, .... This is OEIS sequence A000326.

The jth pentagonal number is

P_j = j(3j - 1) / 2.

We can define negative pentagonal numbers by plugging negative values of j into the equation above, though these numbers don't have the same geometric interpretation. (I think they do have a geometric interpretation, but I forget what it is.)

Euler's pentagonal number theorem

Leonard Euler discovered that the number of even distinct partitions of n equals the number of odd distinct partitions, unless n is a pentagonal number (including negative indices). If n is the jth pentagonal number, then the difference between the number of even and odd distinct partitions of n equals (-1)^j. In symbols,

Here D_e is the number of even distinct partitions and D_o is the number of odd distinct partitions.

Euler discovered this by playing around with power series and noticing that the series involved were generating functions for pentagonal numbers. Jordan Bell has written a commentary on Euler's work and posted it on arXiv.

Mathematica examples

Let's look at the partitions of 12, the 3rd pentagonal number.

IntegerPartions[12] shows there are 77 partitions of 12. We can pick out just the partitions into distinct numbers by selecting partition sets that have no repeated terms, i.e. that have as many elements as their union.

 Select[IntegerPartitions[12], Length[Union[#]] == Length[#] &]

This returns a list of 15 partitions:

 {{12}, {11, 1}, {10, 2}, {9, 3}, {9, 2, 1}, {8, 4}, {8, 3, 1}, {7, 5}, {7, 4, 1}, {7, 3, 2}, {6, 5, 1}, {6, 4, 2}, {6, 3, 2, 1}, {5, 4, 3}, {5, 4, 2, 1}}

Of these sets, 7 have an even number of elements and 8 have an odd number of elements. This matches what Euler said we would get because

7 - 8 = (-1)³.

We'd like to eplore this further without having to count partitions by hand, so let's define a helper function.

 f[list_] := Module[ {n = Length[Union[list]]}, If [n == Length[list], (-1)^n, 0] ]

This function returns 0 for lists that have repeated elements. For sets with no repeated elements, it returns 1 for sets with an even number of elements and -1 for sets with an odd number of elements. If we apply this function to the list of partitions of n and take the sum, we get

D_e(n) - D_o(n).

Now

 Total[Map[f, IntegerPartitions[12]]]

returns -1. And we can verify that it returns (-1)^j for the jth pentagonal number. The code

 Table[Total[Map[f, IntegerPartitions[j (3 j - 1)/2]]], {j, -3, 3}]

returns

 {-1, 1, -1, 1, -1, 1, -1}

We can compute D_e(n) - D_o(n) for n = 1, 2, 3, ..., 12 with

 Table[{n, Total[Map[f, IntegerPartitions[n]]]}, {n, 1, 12}]

and get

 {{1, -1}, {2, -1}, {3, 0}, {4, 0}, {5, 1}, {6, 0}, {7, 1}, {8, 0}, {9, 0}, {10, 0}, {11, 0}, {12, -1}}

which shows that we get 0 unless n is a pentagonal number.

Euler characteristic

Euler's pentagonal number theorem reminds me of Euler characteristic. Maybe there's a historical connection there, or maybe someone could formalize a connection even if Euler didn't make the connection himself. In its most familiar form, the Euler characteristic of a polyhedron is

V - E + F

where V is the number of vertices, E is the number of edges, and F is the number of faces. Notice that this is an alternating sum counting o-dimensional things (vertices), 1-dimensional things (edges), and 2-dimensional things (faces). This is extended to higher dimensions, defining the Euler characteristic to be the alternating sum of dimensions of homology groups.

We can write D_e(n) - D_o(n) to make it look more like the Euler characteristic, using D_k(n) to denote the number of distinct partitions of size k.

D₀(n) - D₁(n) + D₂(n) - ...

I suppose there's some way to formulate Euler's pentagonal number theorem in terms of homology.

The post Partitions and Pentagons first appeared on John D. Cook.