Difference between revisions of "1986 USAMO Problems/Problem 5"

Latest revision as of 13:32, 30 August 2018

Problem

By a partition $\pi$ of an integer $n\ge 1,$ we mean here a representation of $n$ as a sum of one or more positive integers where the summands must be put in nondecreasing order. (E.g., if $n=4,$ then the partitions $\pi$ are $1+1+1+1,$ $1+1+2,$ $1+3, 2+2,$ and $4$ ).

For any partition $\pi,$ define $A(\pi)$ to be the number of $1$ 's which appear in $\pi,$ and define $B(\pi)$ to be the number of distinct integers which appear in $\pi$ (E.g., if $n=13$ and $\pi$ is the partition $1+1+2+2+2+5,$ then $A(\pi)=2$ and $B(\pi) = 3$ ).

Prove that, for any fixed $n,$ the sum of $A(\pi)$ over all partitions of $\pi$ of $n$ is equal to the sum of $B(\pi)$ over all partitions of $\pi$ of $n.$

Solution

Let $S(n) = \sum\limits_{\pi} A(\pi)$ and let $T(n) = \sum\limits_{\pi} B(\pi).$ We will use generating functions to approach this problem -- specifically, we will show that the generating functions of $S(n)$ and $T(n)$ are equal.

Let us start by finding the generating function of $S(n).$ This function counts the total number of 1's in all the partitions of $n.$ Another way to count this is by counting the number of partitions of $n$ that contain $x$ 1's and multiplying this by $x,$ then summing for $1\leq x \leq n.$ However, the number of partitions of $n$ that contain $x$ 1's is the same as the number of partitions of $n-x$ that contain no 1's, so

$S(n) = \sum_{k=1}^n k\cdot (\text{\# of partitions of }n-k\text{ with no 1's}).$

The number of partitions of $m$ with no 1's is the coefficient of $x^m$ in

$\begin{align*} 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*}$

Note that there is no $(1+x+x^2+x^3+\ldots)$ term in $F(x)$ because we cannot have any 1's in the partition.

Let $c_m$ be the coefficient of $x^m$ in the expansion of $F(x),$ so we can rewrite it as $F(x)=c_0+c_1x+c_2x^2+c_3x^3+\ldots.$ We wish to compute $S(n)=1\cdot c_{n-1}+2\cdot c_{n-2}+\ldots+n\cdot c_0.$

Consider the power series $G(x)=(x+2x^2+3x^3+4x^4+\ldots)F(x).$

$\begin{align*} 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*}$

If we expand the first line, we see that the coefficient of $x^n$ in $G(x)$ for any $n$ is $1\cdot c_{n-1}+2\cdot c_{n-2}+\ldots+n\cdot c_0,$ which is exactly $S(n)$ ! So by definition, $G(x)=\frac{x}{1-x} \prod\limits_{i=1}^{\infty}\frac{1}{1-x^i}$ is the generating function of $S(n).$

Now let's find the generating function of $T(n).$ Notice that counting the number of distinct elements in each partition and summing over all partitions is equivalent to counting how many partitions of $n$ contain i and then summing for all $1\leq i \leq n.$

So,

$T(n) = \sum_{k=1}^n k\cdot (\text{\# of partitions of }n\text{ that contain a }k).$

However, the number of partitions of n that contain a $i$ is the same as the total number of partitions of $n-i,$ so $T(n) = \sum_{k=1}^n k\cdot (\text{\# of partitions of }n-k).$

The generating function for the number of partitions is $\begin{align*} 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*}$

Let's write the expansion of $P(x)$ as $P(x)=d_0+d_1x+d_2x^2+d_3x^3+\ldots,$ so we wish to find $T(n)=d_0+d_1+d_2+\ldots+d_{n-1}.$

Consider the power series $H(x)=(x+x^2+x^3+x^4+\ldots)P(x).$

$\begin{align*} 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+\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*}$

If we expand the first line, we see that the coefficient of $x^n$ in $H(x)$ for any $n$ is $d_{n-1}+d_{n-2}+\ldots+d_0,$ which is precisely $T(n).$ This means $H(x)$ is the generating function of $T(n).$

Thus, the generating functions of $S(n)$ and $T(n)$ are the same, so $S(n)=T(n)$ for all $n$ and we are done.

~Peggy

@@ Line 1: / Line 1: @@
 == Problem ==
-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>).
+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>, 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>).
+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>, 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>.
+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 ==
-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 <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>. 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
+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>\begin{align*}
+<cmath>S(n) = \sum_{k=1}^n k\cdot (\text{\# of partitions of }n-k\text{ with no 1's}).</cmath>
-S(n) &= 1*(\text{\# of partitions of n-1 with no 1's})\\ &+ 2*(\text{\# of partitions of n-2 with no 1's})\\ &\cdots \\ &+ n*(\text{\# of partitions of 0 with no 1's})
-\end{align*}</cmath>
 The number of partitions of <math>m</math> with no 1's is the coefficient of <math>x^m</math> in
 <cmath>\begin{align*}
-F(x) &= (1+x^2+x^4+\cdots)(1+x^3+x^6+\cdots)(1+x^4+x^8+\cdots)\cdots \\ &= \prod\limits_{i=2}^{\infty}\frac{1}{1-x^i}
+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+\cdots)</math> term in <math>F(x)</math> because we cannot have any 1's in the partition.
+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+\cdots</math>. We wish to compute <math>S(n)=1*c_{n-1}+2*c_{n-2}+\cdots+n*c_0</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+\cdots)F(x)</math>:
+Consider the power series <math>G(x)=(x+2x^2+3x^3+4x^4+\ldots)F(x).</math>
 <cmath>\begin{align*}
-G(x) &= (x+2x^2+3x^3+4x^4+\cdots)(c_0+c_1x+c_2x^2+c_3x^3+\cdots)\\ &= x(1+2x+3x^2+4x^3+\cdots) \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}
+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>
-Looking at the second line, we see that the coefficient of <math>x^n</math> in <math>G(x)</math> for any <math>n</math> is <math>1*c_{n-1}+2*c_{n-2}+\cdots+n*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>.
+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>
 So,
-<cmath>\begin{align*}
+<cmath>T(n) = \sum_{k=1}^n k\cdot (\text{\# of partitions of }n\text{ that contain a }k).</cmath>
-T(n) &= 1*(\text{\# of partitions of n that contain a 1})\\ &+ 2*(\text{\# of partitions of n that contain a 2})\\ &\cdots \\ &+ n*(\text{\# of partitions of n that contain a n})
-\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>T(n) = \sum_{k=1}^n k\cdot (\text{\# of partitions of }n-k).</cmath>
-T(n) &= 1*(\text{\# of partitions of n-1})\\ &+ 2*(\text{\# of partitions of n-2})\\ &\cdots \\ &+ n*(\text{\# of partitions of 0})
-\end{align*}</cmath>
 The generating function for the number of partitions is
 <cmath>\begin{align*}
-P(x) &= (1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^3+x^6+\cdots)\cdots \\ &= \prod\limits_{i=1}^{\infty} \frac{1}{1-x^i}.
+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>
-Let's write the expansion of P(x) as <math>P(x)=d_0+d_1x+d_2x^2+d_3x^3+\cdots</math>, so we wish to find <math>T(n)=d_0+d_1+d_2+\cdots+d_{n-1}</math>.
+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+\ldots)P(x).</math>
-Consider the power series <math>H(x)=(x+x^2+x^3+x^4+\cdots)P(x)</math>:
 <cmath>\begin{align*}
-H(x) &= (x+x^2+x^3+x^4+\cdots)(d_0+d_1x+d_2x^2+d_3x^3+\cdots) \\
+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+\cdots) \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}
+&= 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>
-Looking at the second line, we see that the coefficient of <math>x^n</math> in <math>H(x)</math> is <math>d_{n-1}+d_{n-2}+\cdots+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>.
+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.

1986 USAMO (Problems • Resources)
Preceded by Problem 4	Followed by Last Question
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "1986 USAMO Problems/Problem 5"

Latest revision as of 13:32, 30 August 2018

Problem

Solution

See Also