2
$\begingroup$

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??

$\endgroup$
2
$\begingroup$

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.

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