Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (→‎Solution)
m (→‎Solution)
Line 15: Line 15:
 
\end{align*}</cmath>
 
\end{align*}</cmath>
  
−
The number of partitions of <math>m</math> with no 1's is the coefficient of <math>x^m</math> in <math>F(x)=(1+x^2+x^4+\cdots)(1+x^3+x^6+\cdots)(1+x^4+x^8+\cdots)\ldots=\prod\limits_{i=2}^{\inf}\frac{1}{1-x^i}</math>. Let <math>c_m</math> be the coefficient of <math>x^m</math> in the expansion, so we can rewrite this 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>.
+
The number of partitions of <math>m</math> with no 1's is the coefficient of <math>x^m</math> in  
  
−
Consider the power series <math>G(x)=(x+2x^2+3x^3+4x^4+\cdots)\cdot F(x)</math>. The coefficient of <math>x^n</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>!
+
<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}
 +
\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.
 +
 
 +
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>.
 +
 
 +
Consider the power series <math>G(x)=(x+2x^2+3x^3+4x^4+\cdots)F(x)</math>:
  
−
We can simplify the expression for <math>G(x)</math>:\
 
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
−
G(x) &= (x+2x^2+3x^3+4x^4+\cdots)\cdot F(x)\\ &= x(1+2x+3x^2+4x^3+\cdots)\cdot \prod\limits_{i=2}^{\inf}\frac{1}{1-x^i}\\ &= x\cdot\frac{1}{(1-x)^2}\cdot \prod\limits_{i=2}^{\inf}\frac{1}{1-x^i}\\ &= \frac{x}{1-x} \cdot \prod\limits_{i=1}^{\inf}\frac{1}{1-x^i}
+
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}
 
\end{align*}</cmath>
 
\end{align*}</cmath>
  
−
Therefore the generating function of <math>S(n)</math> is <math>G(x)=\frac{x}{1-x} \cdot \prod\limits_{i=1}^{\inf}\frac{1}{1-x^i}</math>.
+
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>.
  
−
Now let's find the generating function of <math>T(n)</math>. Notice that counting 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>.  
  
−
In other words,  
+
So,  
  
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
−
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})
+
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>
 
\end{align*}</cmath>
  
Line 39: Line 46:
 
\end{align*}</cmath>
 
\end{align*}</cmath>
  
−
The generating function for the number of partitions is <math>P(x)=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^3+x^6+\cdots)\cdots=\prod\limits_{i=1}^{\inf} \frac{1}{1-x^i}</math>. 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>.  
+
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}.
 +
\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>.  
  
 
Consider the power series <math>H(x)=(x+x^2+x^3+x^4+\cdots)P(x)=(x+x^2+x^3+x^4+\cdots)(d_0+d_1x+d_2x^2+d_3x^3+\cdots)</math>. 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>.
 
Consider the power series <math>H(x)=(x+x^2+x^3+x^4+\cdots)P(x)=(x+x^2+x^3+x^4+\cdots)(d_0+d_1x+d_2x^2+d_3x^3+\cdots)</math>. 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>.
Line 45: Line 57:
 
<math>H(x)</math> can be simplified:
 
<math>H(x)</math> can be simplified:
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
−
H(x) &= (x+x^2+x^3+x^4+\cdots)P(x)\\ &= x(1+x+x^2+x^3+\cdots)\cdot  \prod\limits_{i=1}^{\inf} \frac{1}{1-x^i}\\ &= x\cdot \frac{1}{1-x} \cdot \prod\limits_{i=1}^{\inf} \frac{1}{1-x^i}\\ &= \frac{x}{1-x} \cdot \prod\limits_{i=1}^{\inf} \frac{1}{1-x^i}
+
H(x) &= (x+x^2+x^3+x^4+\cdots)P(x)\\ &= x(1+x+x^2+x^3+\cdots)\cdot  \prod\limits_{i=1}^{\infty} \frac{1}{1-x^i}\\ &= x\cdot \frac{1}{1-x} \cdot \prod\limits_{i=1}^{\infty} \frac{1}{1-x^i}\\ &= \frac{x}{1-x} \cdot \prod\limits_{i=1}^{\infty} \frac{1}{1-x^i}
 
\end{align*}</cmath>
 
\end{align*}</cmath>
  
−
Thus, the generating functions of <math>S(n)</math> and <math>T(n)</math> are the same, which means <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.
  
 
~Peggy
 
~Peggy

Revision as of 11:16, 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

\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})\\ &\cdots \\ &+ n*(\text{\# of partitions of 0 with no 1's}) \end{align*}

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+\cdots)(1+x^3+x^6+\cdots)(1+x^4+x^8+\cdots)\cdots \\ &= \prod\limits_{i=2}^{\infty}\frac{1}{1-x^i} \end{align*}.

Note that there is no $(1+x+x^2+x^3+\cdots)$ 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+\cdots$. We wish to compute $S(n)=1*c_{n-1}+2*c_{n-2}+\cdots+n*c_0$.

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

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

Looking at the second line, we see that the coefficient of $x^n$ in $G(x)$ for any $n$ is $1*c_{n-1}+2*c_{n-2}+\cdots+n*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,

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

However, the number of partitions of n that contain a $i$ is the same as the total number of partitions of $n-i$, so \begin{align*} 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*}

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

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

Consider the power series $H(x)=(x+x^2+x^3+x^4+\cdots)P(x)=(x+x^2+x^3+x^4+\cdots)(d_0+d_1x+d_2x^2+d_3x^3+\cdots)$. The coefficient of $x^n$ in $H(x)$ is $d_{n-1}+d_{n-2}+\cdots+d_0$, which is precisely $T(n)$. This means $H(x)$ is the generating function of $T(n)$.

$H(x)$ can be simplified: \begin{align*} H(x) &= (x+x^2+x^3+x^4+\cdots)P(x)\\ &= x(1+x+x^2+x^3+\cdots)\cdot \prod\limits_{i=1}^{\infty} \frac{1}{1-x^i}\\ &= x\cdot \frac{1}{1-x} \cdot \prod\limits_{i=1}^{\infty} \frac{1}{1-x^i}\\ &= \frac{x}{1-x} \cdot \prod\limits_{i=1}^{\infty} \frac{1}{1-x^i} \end{align*}

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

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1986_USAMO_Problems/Problem_5&oldid=97531"