# Distinct balls into distinct boxes with a minimal number of balls in each box

Find the number of ways to distribute $8$ distinct balls into $3$ distinct boxes if each box must hold at least $2$ balls.

The stars and bars approach would not work because the balls are non-identical. Stirling Numbers of the second kind would also not work directly, because each box doesn't just have to be non-empty; they must contain at least $2$ balls each.

I tried the following approach: Since each box must contain at least $3$ balls each, then the $8$ distinct balls must be divided into distinct partitions of sizes $2,2,4$ or $2,3,3$.

For the first case, we choose $2$ of the $8$ balls for the first partition, $2$ of the $6$ remaining balls for the second partition, and $4$ of the $4$ remaining balls for the third partition. Since the partitions are distinct, we multiply by $3!$ to give:

$$\binom{8}{2}\binom{6}{2}\binom{4}{4}3!$$

Apply the same approach, the number of ways for the second case is:

$$\binom{8}{2}\binom{6}{3}\binom{3}{3}3!$$

Hence, the total number of ways is

$$\binom{8}{2}\binom{6}{2}\binom{4}{4}3! +\binom{8}{2}\binom{6}{3}\binom{3}{3}3!$$

Is my approach valid? Also, is it possible to transform the question to make use of Stirling numbers of the second kind?

$8=4+2+2=2+4+2=2+2+4$ gives $3\times\frac{8!}{4!2!2!}$ possibilities.

$8=2+3+3=3+2+3=3+3+2$ gives $3\times\frac{8!}{2!3!3!}$ possibilities.

So not $3!$ but $3$ as extra factor to avoid double counting.

edit

Label the boxes: box1, box2 and box3.

Number of possibilities to end up with $4$ balls in box1: $\binom{8}{4}\binom{4}{2}\binom{2}{2}=\frac{8!}{4!2!2!}=420$.

The same for $4$ balls in box2 and the same for $4$ ballsi in box3. The events are disjoint, so this amounts in $3\times 420$ possibilities for ending up with $4$ balls in one of the boxes.

Number of possibilities to end up with $2$ balls in box1 and $3$ balls in the other boxes: $\binom{8}{2}\binom{6}{3}\binom{3}{3}=\frac{8!}{2!3!3!}=560$.

The same for $2$ balls in box2 and $3$ in box1 and box3. Also the same for $2$ balls in box3 and $3$ in box1 and box2. The events are disjoint, so this amounts in $3\times 560$ possibilities for ending up with $2$ balls in one of the boxes and $3$ in the other boxes.

• This seems to work for smaller cases! ... but could you elaborate more? If $\{A, B\}, \{C,D\}, \{E,F,G,H\}$ is a possible partitioning, then why not multiply by $3!$ to permute the partitions? – Yiyuan Lee Aug 16 '14 at 8:56
• I must think it over and do not exclude that I made a mistake. After $5$ minutes I will delete. Later I hope to come back. – drhab Aug 16 '14 at 9:05
• $\left\{ \left\{ A,B\right\} ,\left\{ C,D\right\} ,\left\{ E,F,G,H\right\} \right\}$ and $\left\{ \left\{ C,D\right\} ,\left\{ A,B\right\} ,\left\{ E,F,G,H\right\} \right\}$ are allready different choices. However $\left\{ \left\{ C,D\right\} ,\left\{ A,B\right\} ,\left\{ E,F,G,H\right\} \right\}$ also appears as rearrangement of $\left\{ \left\{ A,B\right\} ,\left\{ C,D\right\} ,\left\{ E,F,G,H\right\} \right\}$. So it is counted double. – drhab Aug 16 '14 at 10:50

Associate a different colour to each of the three boxes; then you are looking for the number of ways to colour the balls such that the frequency vectors of colours used is one of $$(2,2,4), (2,3,3), (2,4,2), (3,2,3), (3,3,2), (4,2,2)$$ The number for each of these colourings is given by a trinomial coefficient, and by symmtry one can simply compute $$3\binom8{2,2,4}+3\binom8{2,3,3} = 3\times(420+560) = 2940.$$

So basically your approach is correct, but your rather unclearly motivated multiplication by $3!=6$ is not right; rather, each pattern should be multiplied by the number of its distinct permutations, which happens to be$~3$ here both for $(2,2,4)$ and for $(2,3,3)$.