Show that the number of partitions of $n$ into $k$ parts that are all $m$ or less is

444 Views Asked by At

Full problem: Show that the number of partitions of $n$ into $k$ parts that are all $m$ or less is the number of partitions of $km-n$ into fewer than $m$ parts that are all $k$ or less.

I'm a little confused about how to show this, I tried drawing a Ferrer's diagram, because it's reminding me a little but of identifying self-conjugate partitions but I'm not sure... Can anyone help with this?

1

There are 1 best solutions below

4
On

Hint: Consider the $k \times m$ rectangle into which the partition diagrams of both types fit and find a bijection between the two types:

$$\begin{matrix} {\color{red} \bullet} &{\color{red} \bullet} & {\color{red} \bullet} & {\color{blue} \bullet} \\ {\color{red} \bullet} &{\color{red} \bullet} & {\color{blue} \bullet}&{\color{blue} \bullet} \\ {\color{red} \bullet} & {\color{red} \bullet} &{\color{blue} \bullet} &{\color{blue} \bullet} \\ {\color{red} \bullet}& {\color{blue} \bullet}& {\color{blue} \bullet} &{\color{blue} \bullet}\end{matrix}$$