Why does product rule fail here? (Combinatorics)

Question

I want to find the number of ways to pick $2$ balls out of a box of $4$ balls.

I know that ${}^nC_r$ is the number of ways of selecting $r$ objects from $n$, so the number of ways to pick $2$ balls out of a box of $4$ is simply ${}^4C_2=6$.

Now I want to to do the same but by using product rule this time.

Number of ways to choose first ball is $4$ and number of ways to choose second is $3$ but $4 \cdot 3=12$ and I understand that's because I've counted the same combination twice. For example, say the $4$ balls are $B_1,B_2,B_3,B_4$ then I have once selected $\{B_1,B_2\}$ and then $\{B_2,B_1\}$.

Now here's my question: Why did the product rule fail here? I followed exactly what that rule told me to, but I still ended up with an incorrect answer? Let me be more specific— I think the product rule as it is stated is incomplete but I cannot exactly put my finger on what condition is missing from the rule to make it true.

Note: My question is not "How did I end up over counting?" I know that. My question is "Why did the product rule fail?"

Answer 1

Whenever you want to apply a theorem such as the product rule, you need to verify the assumptions of the theorem. The product can be stated as follows:

If you have a tree where the root vertex has $a$ children, and each child of the root has $b$ children, then the number of grandchildren of the root vertex is $a\times b$.

In order to apply the product rule to a problem, you need to find a tree in the form described above whose bottom-most vertices are in bijective correspondence with whatever you are trying to count. In fact, it is possible to find a tree diagram which describes choosing two unordered objects from a set of size 4:

          Has 1 -- {1, 4}
       / 
 Has 4 -- Has 2 -- {2, 4}
 /     \
.         Has 3 -- {3, 4}
 \
  \              Missing 1 -- {2, 3}
   \          /  
    Missing 4 -- Missing 2 -- {1, 3}
              \ 
                 Missing 3 -- {1, 2}

Since the root has $2$ children, and both children of the root have $3$ children, and since the grandchildren of the root are labeled with each subset of $\{1,2,3,4\}$ of size two exactly once, the product rule implies that the number of subsets is $3\times 2$. This matches the usual value of $\binom 42=\frac{4!}{2!2!}$.

So you see, the product rule can apply to this problem. But you are asking, why does the product rule not imply there are $4\times 3$ sets? Well, simply because there does not exist a tree with $4$ branches at top, where each child has $3$ branches, and the leaves are labeled by the subsets of $\{1,2,3,4\}$ with size $2$.

---

All in all, it is not valid to ask "Why does the product rule fail?" The product rule is a tool which is always true; it cannot fail. The only thing that can fail is a specific attempt at applying the product rule, and it fails because the assumptions of the theorem are not verified. However, since you have not told us how you attempted to apply the product rule to this problem (you simply wrote $4\times 3$, without verifying the assumptions of the product rule), there is no way for us to answer why your attempt at applying it failed. This is why I downvoted your question; you left out this important context.

Answer 2

tl;dr: The rule as written in Wikipedia is perhaps slightly misleading and maybe even incomplete.

The product rule, as stated in Wikipedia says that if there are $a$ ways of doing something and $b$ ways of doing another thing, then the total number of ways of doing both things is $ab$.

So you're assuming for your case, $a=4$ and $b=3$.

But that isn't quite true! For starters, the number of ways to pick the second thing is conditional on the number of ways to do the first thing. Wikipedia never formally defines this rule, but this is mentioned specifically in the following lecture notes: the product rule only holds for independent events.

So what happens when you don't have independent events? You discard invalid instances. Why does it remove so many cases? Because your conditional is a lot more complicated than it seems. When doing a count, you actually need to account for valid cases which have already been counted.

Think of the whole counting exercise as a series of you picking two different balls with the goal of finding distinct pairs, each conditioned on what you have already picked. For example, one step may look like:

How many ways can I pick my second ball, conditioned on the fact that my first ball was $B_2$, and that I already saw the pair $(B_1,B_2)$?

Your conditional here is not just the first ball you picked, but also what pairs you have seen before. So, the number of choices you have is effectively less.

Edit: As Arturo pointed out in a comment, the product rule tells you how many ways there are to draw a first ball followed by a second ball, agnostic of whatever choices you may have made in previous draws. That is not the experiment you want. For a draw to be valid, you must draw a fresh pair, irrespective of order. Consider the following: you do the following draws: $$(1,2),(1,3),(4,1).$$ Now you want to do your fourth draw. Technically, you've drawn $1$ on the first draw only twice. So you should have one more turn, right? But actually you don't, because the irrelevance of order means that $(4,1)$ took care of that. How do you get $4\times 3$? For every one of the four balls, you should get three tries. But here you don't. Because You don't just care about how many ways to draw a first ball and a second ball, you care about the pair itself. The answer to the former is what the product rule gives you.