2
$\begingroup$

How many ways dividing $n$ different balls into 5 buckets, so the first bucket must contain at least $3$ balls.

My approach to the question is:

  1. Lets choose 3 balls to put in the first cell = ${n \choose 3}$
  2. Divide the rest $n-3$ balls between the 5 buckets = $5^{n-3}$

Now using the Rule of product the answer is:

${n \choose 3}5^{n-3}$

Why is my solution incorrect?

  • 0
    @sigma.z.1980: No, the other $n-3$ balls are divided among all $5$ buckets: the first must contain **at least** $3$ balls, not exactly $3$.2011-09-25

2 Answers 2

4

Your solution is incorrect because you’re counting some arrangements more than once. Suppose that the balls are numbered $1$ through $n$. Consider the arrangement that has balls $1,2,3$, and $4$ in the first bucket and every other ball in the second bucket. You’ll count this once when you put balls $1,2$, and $3$ in the first bucket initially. You’ll count it again when you put balls $1,2$, and $4$ in the first bucket initially. And you’ll count it two more times, once when the ‘insurance’ balls are $1,3,4$ and once when they’re $2,3,4$. You end up counting that one arrangement four times. An arrangement with $5$ balls in the first bucket gets counted $\binom53 = 10$ times, and it gets worse from there. Try robjohn’s hint: count the bad distributions instead of the good ones.

  • 0
    this answers the question asked (+1).2011-09-25
3

The number of ways to have exactly $2$ balls in the first bucket is $\binom{\vphantom{2}n}{2}4^{n-2}$ (choose $2$ to put in the first bucket, and $n-2$ into the other $4$); exactly $1$ ball in the first bucket is $\binom{n}{1}4^{n-1}$; and exactly $0$ balls in the first bucket is $\binom{n}{0}4^n$. The total number of ways to put $n$ balls in $5$ buckets is $5^n$.