1986 USAMO Problems/Problem 5
Problem
By a partition of an integer we mean here a representation of as a sum of one or more positive integers where the summands must be put in nondecreasing order. (E.g., if then the partitions are and ).
For any partition define to be the number of 's which appear in and define to be the number of distinct integers which appear in (E.g., if and is the partition then and ).
Prove that, for any fixed the sum of over all partitions of of is equal to the sum of over all partitions of of
Solution
Let and let We will use generating functions to approach this problem -- specifically, we will show that the generating functions of and are equal.
Let us start by finding the generating function of This function counts the total number of 1's in all the partitions of Another way to count this is by counting the number of partitions of that contain 1's and multiplying this by then summing for However, the number of partitions of that contain 1's is the same as the number of partitions of that contain no 1's, so
The number of partitions of with no 1's is the coefficient of in
Note that there is no term in because we cannot have any 1's in the partition.
Let be the coefficient of in the expansion of so we can rewrite it as We wish to compute
Consider the power series
If we expand the first line, we see that the coefficient of in for any is which is exactly ! So by definition, is the generating function of
Now let's find the generating function of Notice that counting the number of distinct elements in each partition and summing over all partitions is equivalent to counting how many partitions of contain i and then summing for all
So,
However, the number of partitions of n that contain a is the same as the total number of partitions of so
The generating function for the number of partitions is
Let's write the expansion of as so we wish to find
Consider the power series
If we expand the first line, we see that the coefficient of in for any is which is precisely This means is the generating function of
Thus, the generating functions of and are the same, so for all and we are done.
~Peggy
See Also
1986 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Last Question | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.