Difference between revisions of "1986 USAMO Problems/Problem 5"
m (→Solution) |
m (→Solution) |
||
Line 21: | Line 21: | ||
We can simplify the expression for <math>G(x)</math>:\ | We can simplify the expression for <math>G(x)</math>:\ | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | G(x) & | + | 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} |
\end{align*}</cmath> | \end{align*}</cmath> | ||
Revision as of 11:54, 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
. Let
be the coefficient of
in the expansion, so we can rewrite this as
. We wish to compute
.
Consider the power series . The coefficient of
for any
is
, which is exactly
!
We can simplify the expression for :\
Therefore the generating function of is
.
Now let's find the generating function of . Notice that counting 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
.
In other words,
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 P(x) as
, so we wish to find
.
Consider the power series . The coefficient of
in
is
, which is precisely
. This means
is the generating function of
.
can be simplified:
Thus, the generating functions of and
are the same, which means
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.