美國數學奧林匹克：劃分數字

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.