0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I think it should be "partitions of $n$ into $k$ OR LESS parts"? $\endgroup$
    – Dzoooks
    Commented Oct 14, 2019 at 1:15
  • $\begingroup$ @Dzoooks no, it's just into k parts! $\endgroup$
    – arad
    Commented Oct 14, 2019 at 1:16

1 Answer 1

2
$\begingroup$

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}$$

$\endgroup$
4
  • $\begingroup$ I'm just a bit unclear on how this rectangle counts both of the number of necessary partitions.. What is the relation supposed to be between km and n? $\endgroup$
    – arad
    Commented Oct 14, 2019 at 1:37
  • $\begingroup$ $n$ is the size of the red partition. $km-n$ is the size of the blue partition. Just do it for a few examples. $\endgroup$
    – Dzoooks
    Commented Oct 14, 2019 at 1:38
  • $\begingroup$ I see it with examples, but to word it properly- If we take a $k•m$ rectangle, and remove the a partition of size $n$ that is $k$ parts, size $m$ or less, then the remaining area is exactly partitioned into fewer than $m$ parts that are k or less. $\endgroup$
    – arad
    Commented Oct 14, 2019 at 1:50
  • $\begingroup$ So there is a bijection between those two types of partitions $\endgroup$
    – arad
    Commented Oct 14, 2019 at 1:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .