# Number of Partitions in which the Two Largest Parts are Equal

Show that for any positive integer $n$, the number of partitions of $n$ in which the two largest parts are equal is $p(n) − p(n − 1)$.

What I have so far:

We can construct a bijection from the set of all partitions of $n-1$ onto the set of all partitions of $n$ that have at least one part equal to one. The bijection is just simply adding a part equal to $1$ to the end of each partition of $n-1$.

What else?

• What is $p(n)$? Apr 26 '15 at 22:07
• The number of partitions of the integer $n$. en.wikipedia.org/wiki/Partition_(number_theory)#Ferrers_diagram Apr 26 '15 at 22:08
• why is your function a bijection? what if there is more than one part equal to $1$? What does a "part equal to $1$" mean, does it mean it has only one element, or is it something more specific, e.g. that one element has to be the number $1$? Apr 26 '15 at 22:15
• @Mirko: It’s all standard terminology; see here, for instance. Apr 26 '15 at 22:23

HINT: Notice that the result is the same as saying that there are $p(n-1)$ partitions of $n$ whose two largest parts are different, so let’s try to prove that instead. Let $p_1+p_2+\ldots+p_m$ be such a partition, where as usual $p_1\ge p_2\ge\ldots\ge p_m$; then

$$(p_1-1)+p_2+\ldots+p_m$$

is a partition of $n-1$. Is this correspondence reversible?

This is equivalent to proving the number of partitions in which the largest two parts are of different sizes is $p(n-1)$.

Given a partition $P$ of size $p(n-1)$ we assign it to the following partition of $n$.

If the partition has its two largest sets with equal size send that partition to the following partition: order the two largest sets depending on the minimimum element and send the partition $P$ to the partition which is equal to $P$ in every sense except for the fact that the $n$ belongs to the set that was one of the largest sets in $P$ and had the minimum element among those sets.

If the partition has its two largest sets with size $P$ then send the partition of $n$ that is identical to $P$ only $n$ belongs to a singleton set.

This function is clearly injective because given a partition of $n$ we can easily recover from which partition of size $n-1$ it came (and it is unique).

On the other hand it is not surjective, this is because if a partition of $n$ comes from a partition of $n-1$ and satisfies that its largest set has the element $n$ then there is always a set that has exactly $1$ element less than the largest set. While there are many partitions of $n$ in which the largest two sets have different sizes which satisfy that the largest set contains $n$, but the second smallest set does not have $1$ element less than the largest set.

In conclusion we gave a function from the set of partitions of $n-1$ to the set of partitions of $n$ in which the two largest sets have different sizes that it injective but no surjective, this tells us there are strictly less partitions of $n-1$ than partitions of $n$ in which the two largest sets have different sizes.

If we aim to finish how you originally started:

Given a number n, consider the number of partitions on n with least part exactly equal to 1.

We see this constraint fixes our last row of the Ferrer's graph, but we may freely partition the remaining n-1. Therefore, the number of partitions on n with least part equal to 1 is p(n-1).

It immediately follows that the number of partitions on n with least part greater than 1 must be p(n) - p(n-1).

Now consider the Ferrer's graph of a partition with least part greater than 1 and conjugate it taking rows to columns and vice versa. What does the resulting (conjugate) Ferrer's graph look like?