# Intution for when to divide a product of binomial coefficients by some factor to avoid double counting

I'm trying to better understand the intuition for when to divide a product of binomial coefficients to avoid double counting.

For instance, here is an example in which it is appropriate to divide by some number to avoid double counting:

How many ways can we form $2$ pairs of students from $4$ students?

My answer: $$\frac{\binom{4}{2}\cdot\binom{2}{2}}{2!}=3.$$

But in this next example we again look at the product of binomial coefficients but do not need to divide by some number to avoid double counting:

How many ways can we form a five card hand in a game of poker such that there are two red cards and three black cards?

My answer: $$\binom{26}{2}\cdot\binom{26}{3}.$$

Now I think it's apparent in this second example that we are first forming a set of two red cards and then appending to it a set of three black cards, but how does this not over count the converse procedure of appending to three black cards two red cards?

When you pick up a "set" of $r$ objects (at once) from a given collection of $n$ objects, you say there are ${n\choose r}$ possible ways to denote the set of these $r$ objects that you can choose. Observe that, since we are talking about sets here, the order in which the elements appear doesn't matter. All we want is $r$ distinct objects.

That is to say, $\{2,1\} = \{1,2\}$

So in the first example, you have 4 students. You have to choose a pair. So total number of ways of selecting a pair of students is ${4 \choose 2} = 6$ Another way of thinking of this problem can be like this: for the first student you have $4$ choices of total students to start with but after having one student chosen you remain with only $3$ different choices of students and hence the number of ways equals $4*3 = 12$ But this time, let's say students were $a,b,c,d$ then observe that you took both $(a,b)$ and $(b,a)$ as different pairs and hence you counted each pair twice and that's why you need to divide by $2$

In the second example which you stated, again it doesn't matters if we first pick up red cards or black cards, all we want is a set of 5 cards in which 2 are red and 3 are black. There are $26$ red and$26$ black cards so total ways of selecting $2$ red and $3$ black cards is ${26 \choose 2}{26 \choose 3}$. As above, a different argument for counting goes as: There are $26$ choices for first red card and $25$ choices for second red card. SImilarly, $26$, $25$, and $24$ choices for 3 black cards respectively. Hence total number of ways is $(26*25)(26*25*24)$. Again, we made the same mistake. We took $(r_1,r_2)$ pair of red card to be different from $(r_2,r_1)$ and similarly for black cards also we took $(b_1,b_2,b_3)$ different from $(b_1,b_3,b_2)$ different from $(b_2,b_1,b_3)$ and so on. So each pair of red card counted twice and each triple of black cards counted $3! = 6$ times. So we divide by a factor of $2*3!$ and we get the answer as $$\frac{26.25}{2}\frac{26.25.24}{3!} = \binom{26}{2}\binom{26}{3}$$

To add, order matters. So let's say, you have $n$ objects and you carry out the following experiment: You pick an object, take a note of it and remove it from the original collection to start with. You repeat this $r$ number of times. Total number of ways selecting $r$ objects remains ${n \choose r}$ but now since the order matters so there are $r!$ ways of rearranging the objects and hence total number of outcomes is $r!{n\choose r} = \frac{n!}{(n-r)!}$. Again, you can count this in a similar other way as we did in examples. This is called sampling without replacement.

• So it seems like we need to be concerned when we are forming $2$ or more subsets that contain the same elements. For instance in the card counting example it is not possible to pick a red card from the set of black cards and vis versa. Whereas in the student example we see that we may pick the same subset from our initial selection that we have already picked from our second selection and vis versa hence creating a pair of identical subsets. Commented Jan 16, 2017 at 19:10
• Yes, exaclty! But sometimes, you might encounter some situation where it is really hard to figure out how many times you have over counted. In that case, I would suggest to think of a particular way in which repetition is definitely avoided or otherwise in other cases, Principle of Inclusion-Exclusion works the best. Commented Jan 16, 2017 at 19:17
• Brilliant! Thanks for this detailed answer. Commented Jan 16, 2017 at 19:20
• Pleasure was all mine! Commented Jan 16, 2017 at 19:21