0
$\begingroup$

I need to distribute $k$ indistinguishable balls to $n$ distinguishable bins. Of course, this is plainly an example where the so-called stars-and-bars technique is helpful: this technique yields an answer of ${k+n-1 \choose n}$. However, I cannot understand why the answer isn't simply $n^k$, since there are $n$ possibilities for the placement of $k$ balls. Could anyone shed some light on this for me?

$\endgroup$
  • $\begingroup$ That was a typo on my part. Thanks for pointing it out! $\endgroup$ – user795305 Sep 30 '14 at 23:24
2
$\begingroup$

If both the $k$ balls and the $n$ bins are indistinguishable it is not a stars and bars problem.

The solution is $\sum_{t=1}^n p(k, t)$, where $p(k,t)$ is the number of partitions of the integer $k$ into $t$ non-empty parts.

Eg: 2 indistinct balls can be placed in 2 indistinct boxes in only $2$ ways: $**|$, $*|*$

Note: $|**$ isn't a solution when the boxes aren't distinguishable: We can't say which is the first or second.


The stars and bars solution, ${k+n-1\choose k}$ is for $k$ indistinguishable balls and $n$ distinct bins. ($k$ Stars and $n-1$ bars)

Eg: 2 indistinct balls can be placed in 2 distinct boxes in $3$ ways: $**|$, $*|*$, $|**$


$n^k$ is the solution to $k$ distinct balls and $n$ distinct bins.

Eg: 2 distinct balls can be placed in 2 distinct boxes in $4$ ways: $AB|$, $A|B$, $B|A$, $|AB$


For completion if we have $k$ distinct balls and $n$ indistinct bins then the solution is $\sum_{t=1}^n S(k, t)$ where $S(k, t)$ is a Stirling Number of the second kind.

Eg: 2 distinct balls can be placed in 2 indistinct boxes in $2$ ways: $AB|$, $A|B$

These are but four of the Twelvefold Way.

$\endgroup$
0
$\begingroup$

It's because everything is indistinguishable. Here's a simple example: Say we have 3 balls and 3 bins. Then we can have the following configations:

All 3 in 1 bin, or

2 in 1 bin, 1 in another,or

1 in 1 bin, 1 in 1 bin, 1 in a third.

So we only have 3 total possibilities here, not $3^3$. Now, if each ball was different from each other ball, AND each bin was different from each other bin, then we would have $3^3$

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