1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "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$). $\endgroup$ – darij grinberg Dec 2 '18 at 10:10
0
$\begingroup$

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

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