What are the total number of ways of distributing $n$ distinct objects in $r$ distinct boxes where arrangement of objects within boxes are also considered and all the boxes are not empty?
I know how to solve the case where empty boxes are allowed. I tried to first select $r$ objects and put them in each box, and then similar to the empty box case, I proceeded, but this will lead to over counting and so I got stuck.
Thanks!.
Best Answer
The distributing can be done by the following algorithm:
First order the objects. This can be done in $n!$ ways.
Then place $r-1$ "dividing sticks" between the objects. There are $n-1$ gaps where you can place a stick. This will produce a division of the objects to the $r$ boxes such that each box is non-empty. This can be done in ${{n-1}\choose{r-1}}$ ways, since you choose the $r-1$ places where you put a stick out of the $n-1$ possible ones.
Each way of doing the algorithm produces a different outcome (since you also consider the order of the elements in the boxes to matter). Also, each outcome can be reached in the algorithm. So the total number of ways is the product
$$n!{{n-1}\choose{r-1}}$$