Online Course Discussion Forum

Combinatorics question

 
 
Picture of Jialin Wang
Combinatorics question
by Jialin Wang - Monday, 7 November 2022, 9:51 PM
 

If you have 5 numbered balls and 5 numbered boxes, then there are 5^5=3125 ways of putting them in the boxes. However, if you first do stars and bars and then determine what the balls' numbers are, the answer is (5+5-1)C5*5!  = 15120, which is not 3125. Where did the overcounting happen?

 
Picture of Dr. Kevin Wang
Re: Combinatorics question
by Dr. Kevin Wang - Tuesday, 8 November 2022, 9:45 AM
 

If a few balls are in the same box, their order does not matter.  That's why it is not simply $5!$ in each case, and that is also why stars and bars cannot apply when the balls are distinguishable.