2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What do you mean by $P(r+n-1, r-1)$ ? Binomial coefficient ? $\endgroup$ – WLOG Dec 24 '14 at 14:18
  • $\begingroup$ @WLOG I updated the question and defined the $P(n,r)$ $\endgroup$ – No one Dec 24 '14 at 15:19
  • $\begingroup$ 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). $\endgroup$ – Alistair Savage Dec 24 '14 at 15:30
  • $\begingroup$ @AlistairSavage No I'm sure the formula is right. it is in Grimaldi discrete math book $\endgroup$ – No one Dec 24 '14 at 15:36
  • $\begingroup$ @RossMillikan: Doesn't it give $P(r,r-1) = r!/1!=r!$ ? $\endgroup$ – Alistair Savage Dec 24 '14 at 15:38
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This gives $P(r+n-1,n)$, which I agree with. $\endgroup$ – Ross Millikan Dec 24 '14 at 15:57
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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