0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Amit Kumar Gupta Apr 26 '15 at 3:55
  • $\begingroup$ Sorry. It is explained below by another user. $\endgroup$ – EmaLee Apr 26 '15 at 4:06
1
$\begingroup$

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

Use the coloring to get a hint for the general argument.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.