Kenneth H. Rosen 7th edition 5.5

Question

How many ways are there to distribute five balls into three boxes if each box must have atleast one ball in it and if the balls are labelled but the boxes are unlabelled?

Answer 1

The problem is distributing $5$ distinct balls $(r = 5)$ among $3$ identical bins $(n = 3)$ such that no bin is empty, which is given by $S(r, n),$ where $S(r, n)$ is Stirling's number of 2nd kind. So, here we need $S(5, 3).$

We have $S(r+1, n) = n* S(r, n) + S(r, n-1)$

Stirling numbers of second kind can be generated as follows:

$1$

$1\quad1$

$1\quad 3\quad 1$

$1\quad 7\quad 6\quad 1$

$1\quad 15\quad 25\quad 10\quad 1$

So, $S(5,3) = 25$ , Giving total number of ways we can distribute $5$ distinct balls into $3$ identical bins such that each bin contains atleast $1$ ball (No bin is empty).

If bin can be empty, Then the total number of ways we can distribute $5$ distinct balls into $3$ identical bins is given by $S(5,1)$ + $S(5,2)$ + $S(5,3)$ = $41$