Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
the other $n-3$ balls are divided between 4 buckets, not 5 –  sigma.z.1980 Sep 25 '11 at 8:48
    
@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$. –  Brian M. Scott Sep 25 '11 at 9:05

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
this answers the question asked (+1). –  robjohn Sep 25 '11 at 9:13

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.