Proof that $ \sum_{i=1}^k p_i = (n-k) $ where $p_i (n)$ is the number of partitions of n into exactly i parts.

Question

I have to proof that

$p_i(n) = p_i(n − i) + p_{i−1}(n − i) + . . . + p_1(n − i).$

for every $ 1 \le i \le n $, where n is number of n partitions has exactly i parts.

Then I have to calculate $p_5(9)$ and $p_5(10)$ which I made like this:

For Ex $p_5(10) = p_1(5) + p_2(5) + p_3(5) + p_4(5) = 6$

$p_1(5)= 1 $

$p_2(5)= 2$

$p_3(5)= 2$

$p_4(5)= 1$

I used to this ferrers diagram.

But I don't know how to proof it I was trying with using Ferres diagram but i cannot see this, the only solution which I've found is:

Given a partition of n with k parts, we can obtain a partition of n − k into k (or fewer) parts but subtracting 1 from each part. The converse construction also works.

This does not help me after reading this many times I cannot still imagine this. Are there maybe more simple proofs? Or maybe graphical proofs?.

I was trying something like this

Rows($k_n$)

x       |xxxxx..
x       |xxxx...  
x       |xxx...
x       |..
$x_n$   |0

but I went with this to nowhere

I will be very thankful for every help.

Answer 1

Let’s look at $p_5(9)$. The Ferrers diagrams of the $5$-part partitions of $9$ are:

$$\begin{array}{lll} \begin{array}{ccc} \bullet&\bullet&\bullet&\bullet&\bullet\\ \bullet\\ \bullet\\ \bullet\\ \bullet \end{array}&\qquad& \begin{array}{ccc} \bullet&\bullet&\bullet&\bullet\\ \bullet&\bullet\\ \bullet\\ \bullet\\ \bullet \end{array}&\qquad& \begin{array}{ccc} \bullet&\bullet&\bullet\\ \bullet&\bullet&\bullet\\ \bullet\\ \bullet\\ \bullet \end{array}\\ \hline \begin{array}{ccc} \bullet&\bullet&\bullet\\ \bullet&\bullet\\ \bullet&\bullet\\ \bullet\\ \bullet \end{array}&\qquad& \begin{array}{ccc} \bullet&\bullet\\ \bullet&\bullet\\ \bullet&\bullet\\ \bullet&\bullet\\ \bullet \end{array} \end{array}$$

The formula that you’re to prove says that

$$\begin{align*} p_5(9)&=p_5(9-5)+p_4(9-5)+p_3(9-5)+p_2(9-5)+p_1(9-5)\\ &=p_1(4)+p_2(4)+p_3(4)+p_4(4)+p_5(4)\;; \end{align*}$$

what do the Ferrers diagrams of these partitions of $4$ look like? They are exactly the parts of the original Ferrers diagams that remain if I throw away the first columns of each. I’ll indicate that by replacing the first column with ‘white’ dots and separating from the rest with a vertical line:

$$\begin{array}{lll} \begin{array}{c|cc} \circ&\bullet&\bullet&\bullet&\bullet\\ \circ\\ \circ\\ \circ\\ \circ \end{array}&\qquad& \begin{array}{c|cc} \circ&\bullet&\bullet&\bullet\\ \circ&\bullet\\ \circ\\ \circ\\ \circ \end{array}&\qquad& \begin{array}{c|cc} \circ&\bullet&\bullet\\ \circ&\bullet&\bullet\\ \circ\\ \circ\\ \circ \end{array}\\ \hline \begin{array}{c|cc} \circ&\bullet&\bullet\\ \circ&\bullet\\ \circ&\bullet\\ \circ\\ \circ \end{array}&\qquad& \begin{array}{c|cc} \circ&\bullet\\ \circ&\bullet\\ \circ&\bullet\\ \circ&\bullet\\ \circ \end{array} \end{array}$$

What’s left of the first diagram is the one $1$-part partition of $4$; what’s left of the second and third diagrams are the two $2$-part partitions of $4$; what’s left of the fourth diagram is the one $3$-part partition of $4$; and what’s left of the fifth diagram is the one $4$-part partition of $4$. (Of course there are no $5$-part partitions of $4$.)

The idea of the proof is to show that this always happens. I’ll assume for now that $n>i$. If you take an $i$-part partition $\pi$ of $n$, draw the Ferrers diagram, and remove the first column, you’ve taken away $i$ dots. Moreover, it’s still true that lengths of the rows are non-increasing from top to bottom. Thus, what’s left is the Ferrers diagram of some partition of $n-i$. It need not have $i$ parts, however; in fact, it can have anywhere from $1$ to $i$ parts, depending on how many parts of $\pi$ were $1$.

Conversely, if you take any partition of $n-i$ with at most $i$ parts and draw its Ferrers diagram, you can add column of $i$ dots to the left of the diagram to get the Ferrers diagram of a partition of $n$ into exactly $i$ parts. These two procedures are inverses of each other: between them they exhibit a bijection between the Ferrers diagrams of $i$-part partitions of $n$, on the one hand, and the Ferrers diagrams of partitions of $n-i$ into at most $i$ parts on the other hand. Thus, it must be the case that

$$p_i(n)=p_1(n-i)+p_2(n-i)+\ldots+p_i(n-i)\;.\tag{1}$$

There is one slightly tricky point, however: what happens if $n=i$? In that case $p_i(n)=p_n(n)=1$, but the righthand side of $(1)$ is

$$p_1(0)+p_2(0)+\ldots+p_n(0)\;,$$

which clearly ought to be $0$. Thus, we must limit ourselves to the case $n>i$.

---

Actually, that’s not quite tree. We can instead define $p_0(0)=1$ and $p_0(n)=0$ if $n>0$, and replace $(1)$ by the formula

$$p_i(n)=p_0(n-i)+p_1(n-i)+p_2(n-i)+\ldots+p_i(n-i)\;;$$

I’ll leave it to you to check that this version works even if $n\le i$.