Proof - The number of partitions of n into at most m parts is the number of partitions into parts whose largest part is at most m

Question

The proof is based on Ferrer's diagram. I know the fact that a partition that can be written with a graphical representation is ferrer's diagram. How do start the proof or implement that to prove that the number of partitions of n into at most m parts is the number of partitions into parts whose largest part is at most m. I.e. pm(n) = πm(n)?

Answer 1

Any proof like this will necessarily be informal initially, but to take a crack at it... Okay first, any time I need examples, I'll use 5 because it only has a few partitions, to wit: $(5);(4,1);(3,2);(3,1,1);(2,2,1);(2,1,1,1);(1,1,1,1,1)$

The main thing to know here is that every Ferrer diagram has a conjugate, formed by mirroring the diagram around its diagonal. For instance, if we take $(2,2,1)$ and reflect it, we get $(3,2)$. (I'm entirely uncertain how to draw these diagrams here without taking up a ton of space, so hopefully you can visualize.)

Let's define $p_k(n)$ as the number of partitions of $n$ with exactly $k$ elements. Also we'll define $q_k(n)$ as the number of partitions of $n$ with largest element $k$, and no larger elements.

Your problem uses "no more than" rather than "exactly," but you can see that $\sum^m_{k=1} p_k (n) = p_m(n)$, and similarly for the "no elements larger than $m$," subbing $q$ for $p$.

From here it suffices to show that $\forall k,n :p_k(n) = q_k(n)$. We proceed informally, starting again with our example of $5$.

First, consider all partitions with exactly two elements. These are $(4,1)$ and $(3,2)$, and each has a different Ferrer diagram. We chose only partitions with exactly two elements, so $p_2(5)=2$. Note that the height of the Ferrer diagram is the number of elements--both Ferrer diagrams have a "height" of $2$.

Now let's look at the conjugates of those diagrams. Flipping $(4,1)$ about the diagonal gives $(2,1,1,1)$, and flipping $(3,2)$ gives $(2,2,1)$. Both of these diagrams have a "width" of $2$--which is also the value of the largest element.

Now consider any Ferrer diagram you wish. It's easy to see that a diagram with height $a$ and width $b$, when flipped diagonally, has height $b$ and width $a$.

Each partition has a different Ferrer diagram, and each diagram (and thus each partition) has a conjugate. For each partition with largest element $b$, its conjugate has $b$ elements, and vice versa.

Therefore, the number of partitions with $k$ elements is the same as the number of partitions with largest element $k$. Which is $\forall k,n :p_k(n) = q_k(n)$.

I hope this (a) helps and (b) actually works as a proof.