# $t(n,r)$ ways of arranging $n-$ objects around $r$ circles

Consider the following combinatorial problem:

Given $r,n\in \mathbb Z$ with $0\lt r\leq n.$ Let $t(n,r)$ denote the number of ways of arranging $n-$distinct objects around $r$ (indistinguishable) circles such that each circle has atleast one object.

Then following relation is true:

$t(n,r)=t(n-1,r-1)+(n-1)t(n-1,r)$

Proof: For simplicity we denote distinct objects by $1,2,\ldots,n$.

Consider the object "1" in any arrangement of $n$ objects around $r$ circles .we have either :

• "1" is the only object in a circle.

in this case $(n-1)$ remaining objects are arranged around $(r-1)$ circles in $t(n-1,r-1)$ ways.

• "1" is mixed with other objects in a circle.

first we arrange $(n-1)$ objects around $r$ circles in $t(n-1,r)$ ways and then place "1" .

Total no. of ways are: $t(n,r)=t(n-1,r-1)+(n-1)t(n-1,r)$

The case 2 is not clear to me how "1" is mixed with other objects in a circle leads to $(n-1)t(n-1,r)$ ways... Can anyone please explain it to me??

Case 2 is basically saying that first forget about '1', now arrange the $n-1$ objects in the $r$ circles. This leads to $t(n-1,r)$ ways. Now remember that if there $x$ objects around a circle there are $x$ spaces between them in which we can place another object.
So in this case there are $n-1$ spaces in which '1' can go and putting it in any of these leads to a different arrangement. So we multiply the two which leads to $(n-1)t(n-1,r)$ ways.