1
$\begingroup$

How many ways can I put $12$ balls into $11$ bins, such that no bin contains more than $2$ balls?

The problem I am having is assigning balls to bins.

$\endgroup$
  • 2
    $\begingroup$ Are balls/bins identical/distinct? $\endgroup$ – Aweygan Mar 20 '17 at 19:51
  • $\begingroup$ Presumably the balls are interchangeable, but are the bins? Is two in the first and one in each other different from two in the last and one in each other? $\endgroup$ – Ross Millikan Mar 20 '17 at 19:51
  • $\begingroup$ Updated the post $\endgroup$ – user2202 Mar 20 '17 at 19:53
  • 2
    $\begingroup$ You have not answered Aweygan's question. If neither the balls nor the bins are distinguishable there are just $6$ ways. $\endgroup$ – Christian Blatter Mar 20 '17 at 20:05
0
$\begingroup$

I am going to assume that the balls are distinguishable but the bins are not.

Every ball can be a loner (i.e. to be in a bin without any other ball) or a partner (to be in a bin together with another ball). The couple of partners can be from $1$ to $6$, so we have six sub-cases. Assuming that we have $k\in[1,6]$ couples of partners, we have $12-2k$ loners: we may choose them in $\binom{12}{12-2k}=\binom{12}{2k}$ ways. After such choice, we have to build the couples of partners: we may do that in $\frac{(2k)!}{k!2^k}$ ways, so the answer is given by

$$ \sum_{k=1}^{6}\binom{12}{2k}\frac{(2k)!}{k! 2^k} = \color{red}{140151}.$$

$\endgroup$
  • $\begingroup$ Can you further explain how to build the couples of partners and why you have to do that step? Why is not going through the possible number of pairs and looking at loners not enough? And btw, you made the correct assumption, I thought I updated the original post it didn't go through I guess. $\endgroup$ – user2202 Mar 20 '17 at 22:04
  • $\begingroup$ @iHopeICanChangeThisLater: to know the loners is not enough to know which balls get coupled. About the coupling procedure, you may consider a permutation of $2k$ objects, resulting in $k$ consecutive couples. You may rearrange such couples in $k!$ ways and freely exchange partnes in every couple. That leads to the mentioned $\frac{(2k)!}{k! 2^k}$ term. $\endgroup$ – Jack D'Aurizio Mar 20 '17 at 22:09
0
$\begingroup$

Here is my answer, going with the assumption that having identical bins means that having two in the first and one in each other is the same as having two in the last and one in each other.

Essentially, we are figuring out different ways to add up to $12$ using eleven numbers, were the numbers being added are various combinations of $0$'s, $1$'s, and $2$'s.

We have:

$$2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 $$

$$2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 0 $$ $$2 + 2+ 2 + 1 + 1 + 1 + 1 + 1 + 1 + 0 + 0 $$ $$2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 0 + 0 + 0 $$ $$2 + 2 + 2 + 2 + 2 + 1 + 1 + 0 + 0 + 0 + 0 $$ $$2 + 2 + 2 + 2 + 2 + 2 + 0 + 0 + 0 + 0 + 0 $$

So the total number of ways to arrange the balls in bins is $6$ ways, which was stated in the comments by Christian Blatter.

If the balls/bins are distinguishable, I would suggest looking at the answer supplied by Jack D'Aurizio

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