Difference between revisions of "1986 USAMO Problems/Problem 5"
m (→Solution) |
|||
(17 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | By a partition <math>\pi</math> of an integer <math>n\ge 1</math> | + | By a partition <math>\pi</math> of an integer <math>n\ge 1,</math> we mean here a representation of <math>n</math> as a sum of one or more positive integers where the summands must be put in nondecreasing order. (E.g., if <math>n=4,</math> then the partitions <math>\pi</math> are <math>1+1+1+1,</math> <math>1+1+2,</math> <math>1+3, 2+2,</math> and <math>4</math>). |
− | For any partition <math>\pi</math> | + | For any partition <math>\pi,</math> define <math>A(\pi)</math> to be the number of <math>1</math>'s which appear in <math>\pi,</math> and define <math>B(\pi)</math> to be the number of distinct integers which appear in <math>\pi</math> (E.g., if <math>n=13</math> and <math>\pi</math> is the partition <math>1+1+2+2+2+5,</math> then <math>A(\pi)=2</math> and <math>B(\pi) = 3</math>). |
− | Prove that, for any fixed <math>n</math> | + | Prove that, for any fixed <math>n,</math> the sum of <math>A(\pi)</math> over all partitions of <math>\pi</math> of <math>n</math> is equal to the sum of <math>B(\pi)</math> over all partitions of <math>\pi</math> of <math>n.</math> |
== Solution == | == Solution == | ||
− | Let <math>S(n) = \sum\limits_{\pi} A(\pi)</math> and let <math>T(n) = \sum\limits_{\pi} B(\pi)</math> | + | Let <math>S(n) = \sum\limits_{\pi} A(\pi)</math> and let <math>T(n) = \sum\limits_{\pi} B(\pi).</math> We will use generating functions to approach this problem -- specifically, we will show that the generating functions of <math>S(n)</math> and <math>T(n)</math> are equal. |
− | Let us start by finding the generating function of <math>S(n)</math> | + | Let us start by finding the generating function of <math>S(n).</math> This function counts the total number of 1's in all the partitions of <math>n.</math> Another way to count this is by counting the number of partitions of <math>n</math> that contain <math>x</math> 1's and multiplying this by <math>x,</math> then summing for <math>1\leq x \leq n.</math> However, the number of partitions of <math>n</math> that contain <math>x</math> 1's is the same as the number of partitions of <math>n-x</math> that contain no 1's, so |
− | <cmath> | + | <cmath>S(n) = \sum_{k=1}^n k\cdot (\text{\# of partitions of }n-k\text{ with no 1's}).</cmath> |
− | S(n) | ||
− | |||
The number of partitions of <math>m</math> with no 1's is the coefficient of <math>x^m</math> in | The number of partitions of <math>m</math> with no 1's is the coefficient of <math>x^m</math> in | ||
<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> | + | 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\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> | + | 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> |
So, | So, | ||
− | <cmath> | + | <cmath>T(n) = \sum_{k=1}^n k\cdot (\text{\# of partitions of }n\text{ that contain a }k).</cmath> |
− | T(n) | ||
− | |||
− | 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> | + | 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> | + | <cmath>T(n) = \sum_{k=1}^n k\cdot (\text{\# of partitions of }n-k).</cmath> |
− | T(n) | ||
− | |||
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)\ldots \\ &= \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}+\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. |
Latest revision as of 13:32, 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.