Difference between revisions of "1986 USAMO Problems/Problem 5"
m (→Solution) |
(→Solution) |
||
Line 12: | Line 12: | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | S(n) &= 1 | + | S(n) &= 1\cdot (\text{\# of partitions of n-1 with no 1's})\\ &+ 2\cdot (\text{\# of partitions of n-2 with no 1's})\\ &\cdots \\ &+ n\cdot (\text{\# of partitions of 0 with no 1's}) |
\end{align*}</cmath> | \end{align*}</cmath> | ||
Line 18: | Line 18: | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | F(x) &= (1+x^2+x^4+\ | + | F(x) &= (1+x^2+x^4+\ldots)(1+x^3+x^6+\ldots)(1+x^4+x^8+\ldots)\ldots \\ &= \prod\limits_{i=2}^{\infty}\frac{1}{1-x^i} |
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | Note that there is no <math>(1+x+x^2+x^3+\ | + | Note that there is no <math>(1+x+x^2+x^3+\ldots)</math> term in <math>F(x)</math> because we cannot have any 1's in the partition. |
− | Let <math>c_m</math> be the coefficient of <math>x^m</math> in the expansion of <math>F(x)</math>, so we can rewrite it as <math>F(x)=c_0+c_1x+c_2x^2+c_3x^3+\ | + | Let <math>c_m</math> be the coefficient of <math>x^m</math> in the expansion of <math>F(x)</math>, so we can rewrite it as <math>F(x)=c_0+c_1x+c_2x^2+c_3x^3+\ldots</math>. We wish to compute <math>S(n)=1\cdot c_{n-1}+2\cdot c_{n-2}+\ldots+n\cdot c_0</math>. |
− | Consider the power series <math>G(x)=(x+2x^2+3x^3+4x^4+\ | + | Consider the power series <math>G(x)=(x+2x^2+3x^3+4x^4+\ldots)F(x)</math>. |
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | G(x) &= (x+2x^2+3x^3+4x^4+\ | + | G(x) &= (x+2x^2+3x^3+4x^4+\ldots)(c_0+c_1x+c_2x^2+c_3x^3+\ldots)\\ &= x(1+2x+3x^2+4x^3+\ldots) \prod\limits_{i=2}^{\infty}\frac{1}{1-x^i}\\ &= x\cdot\frac{1}{(1-x)^2} \prod\limits_{i=2}^{\infty}\frac{1}{1-x^i}\\ &= \frac{x}{1-x} \prod\limits_{i=1}^{\infty}\frac{1}{1-x^i} |
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | If we expand the first line, we see that the coefficient of <math>x^n</math> in <math>G(x)</math> for any <math>n</math> is <math>1 | + | If we expand the first line, we see that the coefficient of <math>x^n</math> in <math>G(x)</math> for any <math>n</math> is <math>1\cdot c_{n-1}+2\cdot c_{n-2}+\ldots+n\cdot c_0</math>, which is exactly <math>S(n)</math>! So by definition, <math>G(x)=\frac{x}{1-x} \prod\limits_{i=1}^{\infty}\frac{1}{1-x^i}</math> is the generating function of <math>S(n)</math>. |
Now let's find the generating function of <math>T(n)</math>. Notice that counting the number of distinct elements in each partition and summing over all partitions is equivalent to counting how many partitions of <math>n</math> contain i and then summing for all <math>1\leq i \leq n</math>. | Now let's find the generating function of <math>T(n)</math>. Notice that counting the number of distinct elements in each partition and summing over all partitions is equivalent to counting how many partitions of <math>n</math> contain i and then summing for all <math>1\leq i \leq n</math>. | ||
Line 38: | Line 38: | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | T(n) &= 1 | + | T(n) &= 1\cdot (\text{\# of partitions of n that contain a 1})\\ &+ 2\cdot (\text{\# of partitions of n that contain a 2})\\ &\cdots \\ &+ n\cdot (\text{\# of partitions of n that contain a n}) |
\end{align*}</cmath> | \end{align*}</cmath> | ||
However, the number of partitions of n that contain a <math>i</math> is the same as the total number of partitions of <math>n-i</math>, so | However, the number of partitions of n that contain a <math>i</math> is the same as the total number of partitions of <math>n-i</math>, so | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | T(n) &= 1 | + | T(n) &= 1\cdot (\text{\# of partitions of n-1})\\ &+ 2\cdot (\text{\# of partitions of n-2})\\ &\ldots \\ &+ n\cdot (\text{\# of partitions of 0}) |
\end{align*}</cmath> | \end{align*}</cmath> | ||
The generating function for the number of partitions is | The generating function for the number of partitions is | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | P(x) &= (1+x+x^2+\ | + | P(x) &= (1+x+x^2+\ldots)(1+x^2+x^4+\ldots)(1+x^3+x^6+\ldots)\cdots \\ &= \prod\limits_{i=1}^{\infty} \frac{1}{1-x^i}. |
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | Let's write the expansion of <math>P(x)</math> as <math>P(x)=d_0+d_1x+d_2x^2+d_3x^3+\ | + | Let's write the expansion of <math>P(x)</math> as <math>P(x)=d_0+d_1x+d_2x^2+d_3x^3+\ldots</math>, so we wish to find <math>T(n)=d_0+d_1+d_2+\ldots+d_{n-1}</math>. |
− | Consider the power series <math>H(x)=(x+x^2+x^3+x^4+\ | + | Consider the power series <math>H(x)=(x+x^2+x^3+x^4+\ldots)P(x)</math>. |
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | H(x) &= (x+x^2+x^3+x^4+\ | + | H(x) &= (x+x^2+x^3+x^4+\ldots)(d_0+d_1x+d_2x^2+d_3x^3+\ldots) \\ |
− | &= x(1+x+x^2+x^3+\ | + | &= x(1+x+x^2+x^3+\ldots) \prod\limits_{i=1}^{\infty} \frac{1}{1-x^i}\\ &= x\cdot \frac{1}{1-x}\prod\limits_{i=1}^{\infty} \frac{1}{1-x^i}\\ &= \frac{x}{1-x} \prod\limits_{i=1}^{\infty} \frac{1}{1-x^i} |
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | If we expand the first line, we see that the coefficient of <math>x^n</math> in <math>H(x)</math> for any <math>n</math> is <math>d_{n-1}+d_{n-2}+\ | + | If we expand the first line, we see that the coefficient of <math>x^n</math> in <math>H(x)</math> for any <math>n</math> is <math>d_{n-1}+d_{n-2}+\ldots+d_0</math>, which is precisely <math>T(n)</math>. This means <math>H(x)</math> is the generating function of <math>T(n)</math>. |
Thus, the generating functions of <math>S(n)</math> and <math>T(n)</math> are the same, so <math>S(n)=T(n)</math> for all <math>n</math> and we are done. | Thus, the generating functions of <math>S(n)</math> and <math>T(n)</math> are the same, so <math>S(n)=T(n)</math> for all <math>n</math> and we are done. |
Revision as of 13:52, 30 August 2018
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.