Solution to puzzle 56: Partition identity

Partitions of 5

Partition	Number of 1s	Number of distinct parts
5	0	1
4 + 1	1	2
3 + 2	0	2
3 + 1 + 1	2	2
2 + 2 + 1	1	2
2 + 1 + 1 + 1	3	2
1 + 1 + 1 + 1 + 1	5	1
Total:	12	12

Let a(n) be the number of 1s in all the partitions of n.  Let b(n) be the sum, over all partitions of n, of the number of distinct parts.  The above table demonstrates that a(5) = b(5).
Show that, for all n, a(n) = b(n).

---

Let p(n) be the number of partitions of n.
We will derive expressions for the number of 1s, and for the number of distinct parts, in terms of p(1), p(2), ... , p(n − 1).

Express the number of 1s in terms of p(1), p(2), ... , p(n − 1)

Take any partition of n − 1, and add a 1.  This gives a partition of n with at least one 1.
Hence, the number of partitions of n which have at least one 1 is p(n − 1).
Similarly, the number of partitions of n which have at least two 1s is p(n − 2).
In general, the number of partitions of n which have at least i 1s is p(n − i), for 1 i n−1.
Finally, the number of partitions of n which have exactly n 1s is, of course, 1.

Now consider the totality of the above enumerations.
We have counted those partitions of n with one 1 exactly once.
The partitions of n with two 1s have been counted twice; once as part of the p(n − 1) partitions with at least one 1, and once as part of the p(n − 2) partitions with at least two 1s.
In general, the partitions of n with i 1s will be counted i times.
The special case of the partition of n with exactly n 1s, is counted n − 1 times with 1 i n−1, and one more time as the sole partition with n 1s.

In other words, the number of times we have counted each partition of n is equal to the number of 1s in the partition.
Hence this count is equal to a(n), the number of 1s in all partitions of n.

Therefore a(n) = p(n − 1) + p(n − 2) + ... + p(1) + 1.

Express the number of distinct parts in terms of p(1), p(2), ... , p(n − 1)

Now consider b(n), the sum, over all partitions of n, of the number of distinct parts.
Another way to look at this sum is to count the number of partitions of n in which the number i appears, and sum those results for 1 i n.

The number of partitions of n in which i appears is p(n − i), for 1 i n−1.
This follows as a₁ + ... + i + ... + a_k = n a₁ + ... + a_n = i.
The special case of i = n adds one further case.

Therefore b(n) = p(1) + p(2) + ... + p(n − 1) + 1.

Therefore a(n) = b(n); the number of 1s is equal to the number of distinct parts.

---

Further reading

1. Partition
2. A Combinatorial Miscellany by Anders Björner and Richard P. Stanley

Source: Richard P. Stanley

Back to top