Prove that $p(n)$ is the number of ways of partition of $n$

Question

For a positive integer $n$, define $p(n)$ to be the number of sets of positive integers $\{ x_1, x_2, \dots, x_k \}$ such that $x_1 > x_2 > \dots > x_k > 0$ and $n = x_1 + x_3 + x_5 + \dots$ (sum of all odd indices element of the set). For example, $p(6) = 11$ since we could have $$ \{ 6 \}, \{ 6, 5 \}, \{ 6, 4 \}, \{ 6, 3 \}, \{ 6, 2 \}, \{ 6, 1 \}, \{ 5, 4, 1\}, \{ 5, 3, 1 \}, \{ 5, 2, 1 \}, \{ 4, 3, 2 \}, \{ 4, 3, 2, 1\} $$ Prove that $p(n)$ is the number of partition of integer $n$ for all $n \in \mathbb{N}$

---

This is from a selection test that already ended. I think it can be done by bijection (maybe generating function), but I have no idea how to continue.

Answer 1

Suppose we are given an admissible set $\{x_1,\dots,x_k\}$. If $k$ is odd, add $0$ to the set so its cardinality is even. Then interpret this set as a strictly decreasing sequence $(a_1,b_1,a_2,b_2,\dots,a_{i+1},b_{i+1})$. There is a unique Young diagram associated to the sequence, constructible as follows:

• Make an L of $a_{i+1}$ squares whose legs point down and right (like $\Gamma$), of which $b_{i+1}$ squares are right of the L's corner (white squares below).
• For $j$ from $i$ to $1$, counting down:
  • Add $a_{j+1}+1$ compulsory squares to the top and left edges of the diagram (blue squares below). The diagram is now not in Young form because of a notch in the top-left, but this is only temporary.
  • Add an L of $a_j-(a_{j+1}+1)$ squares (white below): one square to fill the aforementioned notch, $b_j-(a_{j+1}+1)$ squares to the right of the newly added compulsory squares on top, the remaining squares below the newly added compulsory squares on the left. Young form is now restored.

In each loop iteration we add $a_j$ squares, so the total number of squares in the finished Young diagram is $\sum_{j=1}^{i+1}=n$. It is also easy to see that different sets for which the sum of odd-indexed terms is the same $n$ lead to distinct Young diagrams of $n$ cells. This establishes a bijection between admissible sets whose odd-indexed terms sum to $n$ and Young diagrams of $n$ cells, which themselves are in bijection with partitions of $n$. Thus $p(n)$ as defined in the question is identical to the unrestricted partition function (usually denoted $p(n)$ anyway).