# Counting Problem Concerning the Stars and Bars Technique

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?

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

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.

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$