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
\begin{align*} S(n) &= 1*(\text{\# of partitions of n-1 with no 1's})\\ &+ 2*(\text{\# of partitions of n-2 with no 1's})\\ &\begin{center}\cdots\end{center} \\ &+ n*(\text{\# of partitions of 0 with no 1's}) \end{align*} (Error compiling LaTeX. ! Missing $ inserted.)
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.