1
$\begingroup$

Suppose I have two non-distinguishable balls (for example two white ones) and I color them with red and green, then a combinatorial reasoning could go like this.

  1. Suppose I enumerate the balls, ball one and ball two, and by this distinguish them, and there are $2^2 = 4$ ways to color them
  2. Because they are indistinguishable we had to divide by the number of enumerations, which are $2!$

So in total we have $2^2 / 2! = 2$ different colorings. But obviously wrong, we have

red, red red, green green, green

as different coloring. So what is wrong with this reasoning, which as I see is frequently applied in combinatorial problems?

EDIT: Please consider my other post of a non-trivial conclusion drawn by such an argument, which confuses me cause the proof should be correct...

$\endgroup$
3
  • $\begingroup$ When you divide "by the number of enumerations", you only had to divide the RG, GR colorings (by $2$). That is, these two colorings count as the same and thus overcount. The other two cases, $RR$ and $GG$, did not overcount. $\endgroup$ Mar 13 '14 at 19:44
  • $\begingroup$ so in a general scheme or formula we should first count the elements with different entries, and divide them by #number of entries!? $\endgroup$
    – StefanH
    Mar 13 '14 at 19:56
  • 1
    $\begingroup$ @Stefan: Yes, something like that. For more fun, look up Burnside's lemma and Polya counting sometime. It may help here to not thinking of "dividing" at all, but simply say how many times each colouring has been counted in your "ways". It turns out that $\{R, G\}$ has been counted twice (once as RG and once as GR), but $\{R, R\}$ and $\{G, G\}$ have each been counted only once. $\endgroup$ Mar 13 '14 at 20:19
1
$\begingroup$

The colorings are as follows:

(Red, Red), (Red, Green), (Green, Red), (Green, Green). As the balls are unordered, the colouring (Red, Green) and (Green, Red) are the same, and then you are overcounting.

Think of another similar problem: You have 10 different players, and you want to put them in five pairs. How many different pairs can you form?

$\endgroup$
6
  • $\begingroup$ by pair you mean set, then there are $\binom{10}{2} = 45$ ways. $\endgroup$
    – StefanH
    Mar 13 '14 at 20:09
  • $\begingroup$ That's for ONE of the pairs. You have 8 players left. $\endgroup$ Mar 13 '14 at 20:11
  • $\begingroup$ then it is: $\binom{10}{2}\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2} = 113400$? $\endgroup$
    – StefanH
    Mar 13 '14 at 20:24
  • $\begingroup$ These two selections: { AB, CD, EF, GH, IJ } is the same as { CD, EF, GH, IJ, AB }, and there is where you divide by, in this case, 5! (the number of permutations for five different objects). The reasoning applies similary to your exercise. $\endgroup$ Mar 13 '14 at 20:28
  • $\begingroup$ yes you are right. but here you could write down one single formula, where first something is multiplied and then divided, is it possible to give one single formula in my exercise $\endgroup$
    – StefanH
    Mar 13 '14 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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