Distributing $N$ distinct objects in $R$ distinct boxes when order matters

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)!$

• What do you mean by $P(r+n-1, r-1)$ ? Binomial coefficient ? – WLOG Dec 24 '14 at 14:18
• @WLOG I updated the question and defined the $P(n,r)$ – M a m a D Dec 24 '14 at 15:19
• Are you sure you don't mean $P(n,r) = n!/r!(n-r)!$ ? With your current definition, you don't get the right answer for $n=1$. If there is only one object, there are clearly $r$ ways to put that object in $r$ boxes (the order is irrelevant here). – Alistair Savage Dec 24 '14 at 15:30
• @AlistairSavage No I'm sure the formula is right. it is in Grimaldi discrete math book – M a m a D Dec 24 '14 at 15:36
• @RossMillikan: Doesn't it give $P(r,r-1) = r!/1!=r!$ ? – Alistair Savage Dec 24 '14 at 15:38

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.
• This gives $P(r+n-1,n)$, which I agree with. – Ross Millikan Dec 24 '14 at 15:57
The combinatorial species in question is $$\mathfrak{S}_{=r}(\mathfrak{S}(\mathcal{Z})).$$ This gives the generating function $$\left(\frac{1}{1-z}\right)^r = \frac{1}{(1-z)^r}.$$ Extracting coefficients we get $$n! [z^n] \frac{1}{(1-z)^r}.$$ Apply the Newton binomial to solve this, getting $$n! {n+r-1\choose r-1} = \frac{(n+r-1)!}{(r-1)!}.$$
Place a fixed wall at either end. The remaining things, $n$ objects and $r-1$ walls, can be placed in any order inside the fixed walls, and each arrangement of those $n+r-1$ things gives a different assignment of balls to bins. The walls are interchangeable while the balls are not, so the number of arrangements is $\frac{(n+r-1)!}{(r-1)!}$.