# Combinatorial Proof with Integer Partitions

Give a combinatorial proof of the equality $p_{n}(2n) = p(n)$.

I know I have to do some kind of bijection, but I am new to integer partitions and I do not have a book for this class...

http://en.wikipedia.org/wiki/Partition_(number_theory)#Ferrers_diagram

In case it is not obvious what $p(n)$ stands for:

If $n$ is a positive integer, then a partition of $n$ is a non-increasing sequence of positive integers $p_{1}, p_{2}, . . . , p_{k}$ whose sum is $n$. Each $p_{i}$ is called a part of the partition. We let the function $p(n)$ denote the number of partitions of the integer $n$.

• You say "In case it is not obvious what $p_n$ stands for:" but then go on to describe what $p(n)$ stands for. What is $p_n$? – Amit Kumar Gupta Apr 26 '15 at 3:55
• Sorry. It is explained below by another user. – EmaLee Apr 26 '15 at 4:06

The notation $p_k(n)$ refers either to the number of partitions of $n$ into exactly $k$ parts, or to the number of partitions of $n$ in which the largest part has size $k$; the two are always the same. Thus, you’re being asked to give a combinatorial proof of the fact that $2n$ has the same number of partitions into exactly $n$ parts as $n$ has partitions of any kind whatsoever. Let’s look at a small example, say with $n=3$. The Ferrers diagrams of the $3$ partitions of $3$ are:
$$\begin{array}{ccc} \begin{array}{ccc} \bullet&\bullet&\bullet\\ &\\ & \end{array}&&&\begin{array}{ccc} \bullet&\bullet\\ \bullet\\ & \end{array}&&&\begin{array}{ccc} \bullet\\ \bullet\\ \bullet \end{array} \end{array}$$
The partitions of $6$ into $3$ parts are:
$$\begin{array}{ccc} \begin{array}{ccc} \color{red}{\bullet}&\bullet&\bullet&\bullet\\ \color{red}{\bullet}&&\\ \color{red}{\bullet}&& \end{array}&&&\begin{array}{ccc} \color{red}{\bullet}&\bullet&\bullet\\ \color{red}{\bullet}&\bullet\\ \color{red}{\bullet}&& \end{array}&&&\begin{array}{ccc} \color{red}{\bullet}&\bullet\\ \color{red}{\bullet}&\bullet\\ \color{red}{\bullet}&\bullet \end{array} \end{array}$$