Combinatorics-Partitions of Natural Numbers

Question

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

Answer 1

I would say that you can prove that using generating functions.

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

Then, if you see that this identities have the same generating function, you are done.

Answer 2

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