[Math] Distributing $N$ distinct objects in $R$ distinct boxes when order matters

combinatoricsdiscrete mathematics

There are $P(r+n-1,r-1)$ ways to distribute $n$ objects in $r$ boxes when the order of objects in each box matters. I tried to find out why but I failed.

when the order of objects in each box doesn't matter it equals to $r^n$ because there are $r$ choices for every object and since there are $n$ objects it becomes $r^n$ . But I can't solve this problem when the order of objects in the boxes matter.


UPDATE:

$P(n,r) = n!/(n-r)!$

Best Answer

Think of the boxes as bins arranged in a straight line, separated by walls. You can place the first object in any bin, giving you $r$ choices. But now that object has split its bin in two: another object can be placed before it or after it in its bin. So you have $r+1$ choices for the second object. Similarly you have $r+2$ choices for the third object, etc. This gives $r(r+1)\cdots(r+n-1) = (r+n-1)!/(r-1)!$ possibilities.