4
$\begingroup$

My Answer: I chose to place three balls into one box and two balls in the other two boxes. This can be done three times: $$\binom73\binom42\binom22=\binom{7}{3,2,2}\\ \binom72\binom53\binom22=\binom{7}{2,3,2} \\ \binom72\binom52\binom33=\binom{7}{2,2,3}$$ I'm not sure if this is correct, but we have not covered Stirling numbers yet, so I cannot use that as my explanation. Please help and thank you!

$\endgroup$
6
$\begingroup$

An alternative method, noting that 2/2/3 is the only distribution of seven balls to three boxes with at least two balls in each box:

  • 3 choices for the box with three balls
  • $\binom73=35$ ways to put three balls into that box
  • $\binom42=6$ ways to put two balls into one of the remaining boxes; the third box is then forced to contain the last two balls

This yields $3\cdot35\cdot6=630$ possibilities, and your approach yields the same result but through a longer process.

$\endgroup$
  • $\begingroup$ Of course the solution appear to be the same once one recognises that the three numbers in the OP's solution must be the same by symmetry. $\endgroup$ – Carsten S Jul 15 '17 at 11:38
5
$\begingroup$

Your answer is correct. Here is a variation based upon exponential generating functions.

  • A selection of at least two distinct balls can be encoded as \begin{align*} \frac{x^2}{2!}+\frac{x^3}{3!}+\cdots=e^x-1-x \end{align*}

  • Since we have three boxes we consider \begin{align*} (e^x-1-x)^3\tag{1} \end{align*}

We denote with $[x^n]$ the coefficient of $x^n$ in a series.

Since we are looking for the number of placing $7$ distinct balls we consider the coefficient of $x^7$ in (1) and obtain with some help of Wolfram Alpha

\begin{align*} 7![x^7](e^x-1-x)^3=\color{blue}{630} \end{align*}

$\endgroup$
  • $\begingroup$ Let's say we have a red box, a blue box, and a green box (and the observer is not colorblind). There are $\binom{7}{3}$ ways of placing three balls in the red box, $\binom{4}{2}$ ways of placing two of the remaining four balls in the blue box, and $\binom{2}{2}$ ways of placing the remaining two balls in the green box. Hence, there are $$\binom{7}{3}\binom{4}{2}\binom{2}{2} = \binom{7}{3, 2, 2}$$ ways to distribute the balls so that three are placed in the red box, two are placed in the blue box, and two are placed in the blue box. By symmetry, the answer is $$3\binom{7}{3, 2, 2}$$ $\endgroup$ – N. F. Taussig Jul 19 '17 at 12:31
  • $\begingroup$ @N.F.Taussig: Thanks for your hint! $\endgroup$ – Markus Scheuer Jul 19 '17 at 12:38
  • 2
    $\begingroup$ @N.F.Taussig: I was misleading by myself. Original answer restored. $\endgroup$ – Markus Scheuer Jul 19 '17 at 16:58
  • $\begingroup$ I have written a solution based on your idea of first placing the seven distinguishable ways in three indistinguishable boxes, then arranging the boxes. $\endgroup$ – N. F. Taussig Jul 19 '17 at 19:16
1
$\begingroup$

This solution is a modification of an attempted solution that Markus Scheuer deleted.

First, we count the number of ways seven distinguishable balls can be placed in three indistinguishable boxes if at least two balls are placed in each box. Then we will arrange the boxes.

The only permissible way to distribute the balls is to place three balls in one bag and two each in the other bags.

Method 1: There are $\binom{7}{3}$ ways to select three balls to be placed in one of the boxes. Line up the remaining balls in a row. Take the ball at the left end of the row and place it in an empty box. There are three ways of selecting one of the other three balls to be placed in the same box as that ball. The remaining two balls must be placed in the remaining empty box. Hence, there are $$3\binom{7}{3}$$ ways to place seven distinguishable balls in three indistinguishable boxes.

Method 2: There are $\binom{7}{3}$ ways to place three of the balls in one box. That leaves $\binom{4}{2}$ ways to place two of the remaining four balls in another box. The remaining two balls are place in the third box. That suggests the answer is $$\binom{7}{3}\binom{4}{2}$$ However, since the boxes are indistinguishable, we cannot distinguish between the two boxes that received two balls. Thus, we must multiply the above result by $1/2$. Hence, there are $$\frac{1}{2}\binom{7}{3}\binom{4}{2}$$ ways of distributing seven distinguishable balls to three indistinguishable boxes.

To make the boxes distinguishable, we paint one box blue, one box green, and one box red. There are $3!$ ways to do this. Hence, there are $$3! \cdot 3\binom{7}{3} = 630$$ ways to place seven distinguishable balls in three distinguishable boxes if at least two balls must be placed in each box.

$\endgroup$
  • $\begingroup$ @NFTaussig: Clear and extensive elaboration. Very nice! (+1) $\endgroup$ – Markus Scheuer Jul 19 '17 at 19:38

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.