2
$\begingroup$

We have $n+2$ balls and $n$ bins, in how many ways we can divide the balls between the bins such that there's no empty bin? (Bins are different and numbered)

My attempt: for the first bin we have $n+2$ options, for the second bin $n+1$ options, etc, for the last bin we have 3 options, when every bin has one ball we have two balls left, there are $n$ options for each ball so the final answer is: $\frac {(n+2)!}{2}\cdot n^2$

EDIT: The balls are different. (sorry I forgot to add that)

$\endgroup$
2
$\begingroup$

Since each bin must have at least 1 ball, you only free to choose how to place the remaining two balls. They can either both go in the same bin ($n$ ways to do this) or in different bins ($\binom{n}{2}$ ways to do this). Thus $$ n+\binom{n}{2}=\binom{n+1}{2}. $$

UPDATE: the balls being distinct changes things. There are $\binom{n+2}{n}$ ways to select how to fill the bins with 1 ball each. Then there are $n!$ ways to order each selection for a total of $$ n!\binom{n+2}{n} $$ ways to fill the bins with 1 ball each. The last two balls can either both go in the same bin ($n$ ways to do this) or in different bins ($2\binom{n}{2}$ ways to do this). The factor of two is from the fact that once I have selected the individual bins to put the remaining balls in, there are 2 distinct ways to fill them. Thus $$ n!\binom{n+2}{n}\left(n+2\binom{n}{2}\right). $$

$\endgroup$
  • $\begingroup$ It took me a while to see that $n!\binom{n+2}{n}=\frac {(n+2)!}{2}$ so at least I got that right.. Thanks for the detailed answer. $\endgroup$ – GinKin Feb 26 '15 at 18:24
  • $\begingroup$ I would get too hung up on simplifying the expression. There are lots of ways to proceed. $\endgroup$ – Laars Helenius Feb 26 '15 at 18:25
2
$\begingroup$

The so called Stirling number so the second kind S(n,k) is the number of ways to distribute $n$ different objects over $k$ undistinguished subsets. In this case we have $n+2$ objects and $n$ distinguished bins, so we get $n!S(n+2,n)$ as the number.

Now use the explicit formula from the Wikipedia page.

$\endgroup$
  • $\begingroup$ I really need to remember this. I jump right in to counting a forget about things like the Stirling numbers. $\endgroup$ – Laars Helenius Feb 26 '15 at 18:28
  • $\begingroup$ This leaves us with an expression that has sums no? $\endgroup$ – GinKin Feb 26 '15 at 18:32

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.