Complete the proof and find a bijection

Question

Complete the proof of the following theorem. Show that the described bijection is indeed a bijection; show that this bijection is both an injection and a surjection.

Theorem: For any integers $k$ and $n$ with $n$ $\geq$ $k$ $>$ $1$, the number of partitions of $n$ into $k$ parts, $p_{k}(n)$, is the number of partitions of $(k-1)n$ into $k$ parts that are all less than $n$.

Proof:

Let $\lambda$ be a partition of $n$ into $k$ parts. Since $k$ exceeds $1$, each part is less than $n$. Put the Ferrers diagram of $\lambda$ in a k$\times$n grid of squares so as to cover the northwest corner. Note that there are $kn$ squares in all, $n$ of which are occupied by squares of $\lambda$. Therefore, the complementary squares, when rotated $180^{\circ}$, form the Ferrers diagram of a partition of $(k-1)n$ into $k$ parts, each of which is less than $n$. It is easy to see that the function defined in this way is indeed a bijection from the set of partitions of $n$ into $k$ parts onto the set of partitions of $(k-1)n$ into $k$ parts, all of which are less than $n$.

I am not entirely sure what this is saying, but to I just show that this is just simply a transpose of a matrix?

What I have:

Let the elements of the matrix $A$=$a_{ij}$, where $i$ represents the row number and $j$ represents the column number. So $A^{t}$= $a^{ji}$, and so the transformation is one-to-one. A function is onto if and only if for every $y$ in $A^{t}$ there exists at least one $x$ in $A$ such that $f(x) = y$. Taking, the empty parts of the matrix to be $0$, if we transpose the matrix, then it will be onto.

Sorry if this is bad.

Answer 1

You don't want to look at the transpose of your matrix. That will yield the conjugate of the Ferrers diagram, as it just reflects about the main diagonal. What you want to look at is the "complement" of your Ferrers board in the $k \times n$ grid.

Consider your Ferrers board for $ \lambda \in \Pi_n $ with $ k $ parts sitting in a $ k \times n $ grid. Shade the cells that are in the Ferrers board and look at the unshaded cells (taking up the bottom/right of your matrix). The unshaded cells is your partition of $ k(n-1) $ into $k$ parts with largest part less than $n$.

For surjectivity, notice that applying the process to a $k(n-1)$ partition with $k$ parts, each part less than $n$, results in a partition of $n$ with $k$ parts. Injectivity comes from noticing that the preimage of any $k(n-1)$ partition into $k$ parts, each part less than $n$, is unique.