3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ What is $p(n)$? $\endgroup$ Apr 26 '15 at 22:07
  • $\begingroup$ The number of partitions of the integer $n$. en.wikipedia.org/wiki/Partition_(number_theory)#Ferrers_diagram $\endgroup$
    – EmaLee
    Apr 26 '15 at 22:08
  • $\begingroup$ 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$? $\endgroup$
    – Mirko
    Apr 26 '15 at 22:15
  • $\begingroup$ @Mirko: It’s all standard terminology; see here, for instance. $\endgroup$ Apr 26 '15 at 22:23
2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.