Online Course Discussion Forum

Math Challenge II-A Combinatorics Series

 
 
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.