A partition of n is an increasing sequence of integers with sum n. For example, the partitions of 5 are: 1, 1, 1, 1, 1; 1, 1, 1, 2; 1, 1, 3; 1, 4; 5; 1, 2, 2; and 2, 3. If p is a partition, f(p) = the number of 1s in p, and g(p) = the number of distinct integers in the partition. Show that ∑ f(p) = ∑ g(p), where the sum is taken over all partitions of n.
Solution
Let π(n) be the number of partitions of n. If p = a1, a2, ... , am is a partition of n, then h(p) = 1, a1, ... , am is a partition of n+1 which contains a 1. Moreover, h is obviously a bijection between partitions of n and partitions of n+1 which contain a 1. But h(p) also contains one more 1 than p, so ∑ f(p) for n+1 is ∑ f(p) for n plus π(n). Thus ∑ f(p) for n is 1 + π(1) + π(2) + ... + π(n-1). [Obviously ∑ f(p) for n = 1 is 1.]
Checking, we find π(1) = 1, π(2) = 2, π(3) = 3, π(4) = 5, π(5) = 7. So this formula gives ∑ f(p) for n = 5 is 1 + 1 + 2 + 3 + 5 = 12, which is correct.
Now fix n and consider the number of pairs (p, m), where p is a partition of n containing m. For each p the number of such pairs is g(p). So the total number of such pairs ∑ g(p). But the number of pairs (p, m) for fixed m is just π(n - m) (taking π(0) = 0). So the total is also ∑ π(n - m). So ∑ g(p) = 1 + π(1) + ... + π(n-1) = ∑ f(p).
© John Scholes
jscholes@kalva.demon.co.uk
26 Aug 2002