# Combinatorics-Partitions of Natural Numbers

Let $$R(r,k)$$ denote the number of partitions of the natural number $$r$$ into $$k$$ parts.

1. Show that $$R(r,k)=R(r-1,k-1)+R(r-k,k)$$

2. Show that $$R(n-r,1)+R(n-r,2)+R(n-r,3)+...R(n-r,r)=R(n,r)$$

• Isn't $R(r-1,k-1)$ also the number of partitions of $r$ into $k$ parts where in addition the least part must be $1$? – Lord Shark the Unknown Jan 18 at 8:00
• It must be $R(r,k-1)+R(r-k,k)$. – Takahiro Waki Jan 18 at 8:20
• R(r-1,k-1) is also the number of partitions of r into k parts where the least part must be 1. Even I think this is true 👆 – Saee Jan 18 at 9:42

1. If the smallest part of a partition of $$r$$ into $$k$$ parts is $$1$$, then removing the smallest part leaves a partition of $$r-1$$ into $$k-1$$ parts. If the smallest part is more than $$1$$, the reducing each part by $$1$$ leaves a partition of $$r-k$$ into $$k$$ parts.
2. Take a partition of $$n$$ into $$r$$ parts, and reduce the size of each part by $$1$$. What remains is a partition of $$n-r$$ into $$m$$ parts, for some number $$m$$ between $$1$$ and $$r$$.
Let $$R(n,k)=p_k(n)$$ be the function you have mentioned above. Then it can be expressed as:
$$\sum_{n\geq0} p_k(n)\cdot x^n = x^k\cdot \prod_{k=1}^n \frac{1}{1-x^i}$$