2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Yiyuan Lee Aug 16 '14 at 8:56
  • 1
    $\begingroup$ 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. $\endgroup$ – drhab Aug 16 '14 at 9:05
  • $\begingroup$ $\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. $\endgroup$ – drhab Aug 16 '14 at 10:50
1
$\begingroup$

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

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