Number of ways to partition a set of $n$ indistinguishable items into $r$ groups

Question

I came across the problem where I have to count the number of ways a set of $n$ indistinguishable items can be partitioned into $r$ groups.

For example,

• if $n=2$ and $r=2$, I can do partitioning as follows:
  $*|*$
• if $n=3$ and $r=2$, I can do partitioning as follows:
  $*|**$
• if $n=4$ and $r=2$, I can do partitioning as follows:
  $*|***$
  $**|**$
• if $n=5$ and $r=2$, I can do partitioning as follows:
  $*|****$
  $**|***$

Is there any closed formula / equation which can come up with this count? If not closed, then some summation series which can give this count?

This does resembles to star and bar problems with the difference that in star and bar problems, we have distinguishable groups. That is $(**|***)$ and $(***|**)$ will be counted twice separately. This is not the case here. My primary understanding is that, here we cannot come up with closed formula like in star and bar problems. Am I correct?

Answer 1

The number you are looking for is the partition of a number into $k$ positive parts.

There is no closed formula for this, but one can use the recurrence relation: $$ p_k(n) = p_k(n − k) + p_{k−1}(n − 1) $$ with $$ p_0(0) = 1 \text{ and } p_k(n) = 0 \text{ if } n ≤ 0 \text{ or } k ≤ 0. $$