<s>[INST] Integer partition of n into k parts recurrence I was learning integer partition of a number n into k parts(with minimum 1 in each part) and came across this recurrence :
part(n,k) = part(n-1,k-1) + part(n-k,k) 
But, I cannot understand the logic behind this recurrence. Can someone please help me visualize this recurrence?
 [/INST] 
Let's consider an example: $n=8$ and $k=3$:
\begin{align*}
\\
P(n,k)&=P(n-1,k-1)+P(n-k,k)&\\
\\
P(8,3)&=P(7,2)+P(5,3)&\\
\\
5\quad&=\quad3\qquad+\quad2
\end{align*}

$$ $$

\begin{array}{rlrlrl}
&P(8,3)\qquad=&& P(7,2)\qquad\qquad+&&P(5,3)\\
\hline\\
8&=\color{red}{6+1}+1\qquad& 7&=6+1\\
&=\color{red}{5+2}+1\qquad&&=5+2\\
&=\color{red}{4+3}+1\qquad&&=4+3\\
&=\color{blue}{4+2+2}\qquad&&\qquad &\qquad5&=3+1+1\\
&=\color{blue}{3+3+2}\qquad&&\qquad&\qquad&=2+2+1
\end{array}

Note that the partitions of $P(8,3)$ that have smallest integer part equal to one correspond to the integer partitions of $P(7,2)$ whereas the partitions with smallest integer part $>1$ correspond to the partitions of $P(5,3)$:
\begin{align*}
4+2+2=(3+1+1)+3\\
3+3+2=(2+2+1)+3
\end{align*}
</s>