Online Course Discussion Forum

Math Challenge II-A Combinatorics Series

 
 
JinTina的头像
Math Challenge II-A Combinatorics Series
JinTina - 2022年12月31日 Saturday 10:57
 

Hello,


For problem 5.22, I had a different method but it is wrong, can please find out where the mistake is?


Pick which 2 of the 6 boxes are one color, say for example green. (6 choose 2)=15. then use stars and bars to arrange the other 2 green balls. so (6+2-1 choose 2-1)=7. so (15*7)^3 which is not equal to 120^3. 


Thanks!

 
LensmireJohn的头像
Re: Math Challenge II-A Combinatorics Series
LensmireJohn - 2023年01月3日 Tuesday 11:30
 

Typically when you have phrases like "at least two boxes" you need to be careful with overcounting. For example, what if you pick boxes A and B for the 2 boxes, then boxes C and D get a ball in the stars and bars part. Doesn't that give the exact same outcome as if you pick boxes C and D first, then put balls in A and B in the stars and bars part?

If you wanted to pick the boxes like you are here, you'd need to do three cases for exactly 2 boxes, exactly 3 boxes, or exactly 4 boxes:

  • Exactly 2: $\displaystyle \binom{6}{2} = 15$ ways to pick two boxes, then $\displaystyle\binom{2+2-1}{2-1} = 3$ ways to put the remaining balls in those 2 boxes.
  • Exactly 3: $\displaystyle \binom{6}{3} = 20$ ways to pick three boxes, then $3$ ways to put the remaining ball in one of the boxes.
  • Exactly 4: $\displaystyle \binom{6}{4} = 15$ ways to pick 4 boxes.

Note, $15\cdot 3 + 20\cdot 3 + 15 = 120$ and this would match the method using complementary counting.