How many ways are there to place $7$ distinct balls into $3$ distinct boxes?

is the question I'm confused about.

The solution shows that the correct answer is $3^7$. I'm just confused why this is.

My thinking is that if there are 3 boxes, and 7 possible balls for each box:

number of choices:  7 6 5
individual boxes:  _ _ _

So $7*6*5$ total possibilities...

But clearly, the logic in this problem is the following:

Number of choices: 3 3 3 3 3 3 3
Individual balls:   _ _ _ _ _ _ _

Why is the 1st solution incorrect?

  • 2
    $\begingroup$ There aren't 7 choices for box 1. The question never stated that exactly one ball goes into every box $\endgroup$ – Edward Jiang Dec 13 '14 at 23:56
  • $\begingroup$ @EdwardJiang Ah! This is exactly what i needed. I'm so used to using the first method to solve problems since typical questions ask for rearrangements of words or such. $\endgroup$ – Riptyde4 Dec 13 '14 at 23:59
  • $\begingroup$ Yes, in fact box 1 holds one of the $2^7$ possible subsets of the seven balls. $\endgroup$ – String Dec 13 '14 at 23:59
  • $\begingroup$ To follow up on what Edward said, you did solve a math problem with your first solution, but not the one you were asked. You solved “How many ways are there to put one of seven distinct balls into each of three distinct boxes?” $\endgroup$ – Steve Kass Dec 14 '14 at 0:03

We are given the task of placing 7 balls into 3 jars. Step 1: Place 1st ball, 3 ways to do that. Step 2: Place 2nd ball, 3 ways to do that....Step 7: place last(seventh) ball, 3 ways to do that. By rule of product, we have $3*3*3*3*3*3*3 = 3^7$ ways to accomplish the task. Your method is wrong because assumes we need to put a ball in the first jar. We don't need to put anything in the first jar.

  • $\begingroup$ So the amount of ways to place n distinct objects into k boxes is k^n... $\endgroup$ – Riptyde4 Dec 14 '14 at 0:05
  • $\begingroup$ Exactly. Combinatorics is a tricky subject, keep working at it though and it gets much easier. $\endgroup$ – Dunka Dec 14 '14 at 0:08
  • $\begingroup$ @Riptyde4: Yes! $\endgroup$ – String Dec 14 '14 at 0:10

If we go crazy and try to solve it the hard way by considering what each box contains, we could do as follows:

  1. Box 1 first chooses a number $0\leq a\leq 7$.
  2. Then box 2 gets to choose a number $0\leq b\leq 7-a$.
  3. Finally box 3 is forced to choose $c=7-a-b$.
  4. Then box 1 chooses $a$ balls in $\binom{7}{a}$ ways.
  5. Next box to chooses $b$ of the remaining balls in $\binom{7-a}{b}$ ways.
  6. Finally box 3 is forced to accept the remaining $7-a-b$ balls.

Then we could proceed to make a difficult looking sum of cases and numbers of possibilities:

$$ 3^7=\sum_{a=0}^7\sum_{b=0}^{a-7}\binom{7}{a}\binom{7-a}{b} $$

The simple way, as I see it, is to assign a number to each ball from the set $\{0,1,2\}$. Then a combination of placing the balls corresponds exactly to a seven digit ternary number. Of course there will be $3^7$ of those :-)

This is so easily generalized to $n$ digit base $k$ numbers corresponding to placing $n$ balls in $k$ boxes, thus making $k^n$ setups.

  • $\begingroup$ Very clever, thank you $\endgroup$ – Riptyde4 Dec 14 '14 at 0:10

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.