0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Lord Shark the Unknown Jan 18 at 8:00
  • $\begingroup$ It must be $R(r,k-1)+R(r-k,k)$. $\endgroup$ – Takahiro Waki Jan 18 at 8:20
  • $\begingroup$ 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 👆 $\endgroup$ – Saee Jan 18 at 9:42
2
$\begingroup$
  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$.

$\endgroup$
1
$\begingroup$

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.

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