# Partitions in Combinatorics

Let $$2\leq k\leq n$$. Prove that $$p_k(n)=p_{k-1}(n-1)+p_k(n-k)$$ where $$p_k(n)$$ is the number of partitions of $$n$$ into $$k$$ pieces. Here's my proof:

Proof: Let $$2\leq k\leq n$$. Let $$p_k(n)$$ be the number of partitions of $$n$$ into $$k$$ parts. We can divide the partitions into two classes. First, consider all partitions that contain a part of size 1. By deleting this part, we are left with a partition of $$n-1$$ into $$k-1$$ parts. Thus there are $$p_{k-1}(n-1)$$ partitions in this class. Next, consider all partitions in which every part has size 2. Then by deleting 1 from every part, we are left with a partition of $$n-k$$ into $$k$$ parts. Thus there are $$p_k(n-k)$$ partitions in this class. Therefore, $$p_k(n)=p_{k-1}(n-1+p_k(n-k)$$ with the initial conditions that $$p_1(n)=1$$ and $$p_k(n)=0$$ for $$n.

• "deleting 1 from every part" -> "subtracting $1$ from every part". The proof is correct but maybe worth formalizing more. You're setting up a bijection between the class-1 partitions of $n$ into $k$ parts and the class-1 partitions of $n-1$ into $k-1$ parts, and likewise for class 2. And it is worth saying what the inverse maps are (note you're using the fact that if a partition has a part $1$, then its last part must be $1$). – darij grinberg Dec 2 '18 at 10:10

## 1 Answer

Hint

Let $$P_k(n)$$ be the set of partitions of $$n$$ with exactly $$k$$ parts i.e. $$p_{k}(n)=|P_k(n)|$$. Classify $$\lambda=(\lambda_1,\dots,\lambda_k)\in P_k(n)$$ (where the $$\lambda_i$$ are weakly decreasing and positive) based on whether $$\lambda_k=1$$ or $$\lambda_k>1$$.