1986 USAMO Problems/Problem 5

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})\\ &... \\ &+ 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 $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}^{\inf}\frac{1}{1-x^i}$ . Let $c_m$ be the coefficient of $x^m$ in the expansion, 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*c_{n-1}+2*c_{n-2}+\ldots+n*c_0$ .

Consider the power series $G(x)=(x+2x^2+3x^3+4x^4+\ldots)\cdot F(x)$ . The coefficient of $x^n$ for any $n$ is $1*c_{n-1}+2*c_{n-2}+\ldots+n*c_0$ , which is exactly $S(n)$ !

We can simplify the expression for $G(x)$ : $\begin{align*} G(x) &= G(x)=(x+2x^2+3x^3+4x^4+\ldots)\cdot F(x)\\ &= x(1+2x+3x^2+4x^3+\ldots)\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} \end{align*}$

Therefore the generating function of $S(n)$ is $G(x)=\frac{x}{1-x} \cdot \prod\limits_{i=1}^{\inf}\frac{1}{1-x^i}$ .

Now let's find the generating function of $T(n)$ . Notice that counting 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$ .

In other words, $\begin{align*} T(n) &= 1*(\text{\# of partitions of n that contain a 1})\\ &+ 2*(\text{\# of partitions of n that contain a 2})\\ &... \\ &+ 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)\\ &... \\ &+ n*(\text{\# of partitions of 0})
\end{align*} (Error compiling LaTeX. Unknown error_msg)

The generating function for the number of partitions is $P(x)=(1+x+x^2+\ldots)(1+x^2+x^4+\ldots)(1+x^3+x^6+\ldots)\ldots=\prod\limits_{i=1}^{\inf} \frac{1}{1-x^i}$ . 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)=(x+x^2+x^3+x^4+\ldots)(d_0+d_1x+d_2x^2+d_3x^3+\ldots)$ . The coefficient of $x^n$ in $H(x)$ is $d_{n-1}+d_{n-2}+\ldots+d_0$ , which is precisely $T(n)$ , so $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+\ldots)P(x)\\ &= x(1+x+x^2+x^3+\ldots)\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} \end{align*}$

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

~Peggy

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

1986 USAMO Problems/Problem 5

Problem

Solution

See Also