Why doesn't $\binom{n}{a-b}\binom{n-(a-b)}{b}=\binom{n}{a}$?

Question

We know that the multiplication principle states that if there are $a$ ways of doing $A$ and $b$ ways of doing $B$ once $A$ has happened, then there are $ab$ ways of performing both actions.

Keeping this in mind, suppose that I have a group of $n$ distinct objects and I want to choose $a$ of them. This can obviously be done in $$\binom{n}{a}$$ ways.

However, it would seem that I could also first choose $a-b$ objects followed by another $b$ objects from the group of $n$ objects. Now, the number of ways of choosing the first $a-b$ will clearly be $$\binom{n}{a-b}$$ and once they've been chosen the number of ways of choosing the remaining $b$ items will be $$\binom{n-(a-b)}{b}.$$

---

Question According to the multiplication principle, it seems that the number of ways of choosing $a$ objects from $n$ should be equal to the number of ways of choosing $a-b$ objects from $n$ followed by $b$ objects from $n-(a-b)$ objects. If so, why doesn't $$\binom{n}{a-b}\binom{n-(a-b)}{b}=\binom{n}{a}?$$

Answer 1

Consider an arbitrary subset of $a$ of your $n$ objects. Let's call them $\{x_1, x_2, x_3, \ldots, x_a\}.$ When you count $$ \binom na $$ ways of drawing a subset of size $a,$ you are counting this subset exactly once.

When you choose $a - b$ elements first and then choose another $b$ elements, you count this subset once by choosing the first $a - b$ elements, $\{x_1, x_2, \ldots, x_{a-b}\}.$ But you count it again by choosing the last $a - b$ elements, and again for every other subset of $a - b$ elements among the $a$ elements of $\{x_1, x_2, x_3, \ldots, x_a\}.$

Since there are $$ \binom {a}{a - b} = \binom ab $$ subsets of $a - b$ elements you can choose from among the $a$ elements of $\{x_1, x_2, x_3, \ldots, x_a\},$ you count this subset exactly $ \binom ab $ times. The same thing happens for every other subset of $a$ elements from among your original $n$ elements.

This is a very common type of overcounting error: first satisfy the condition partway, and then satisfy it the rest of the way, overlooking the fact that for a single desired outcome there are multiple ways to satisfy it partway. This case is particularly fortunate, however, in that every single outcome is overcounted the exact same number of times.

So what we have discovered is that choosing $a - b$ items from $n$ items, and then choosing $b$ items from the remaining $n - (a - b)$ items, can be done in exactly $\binom ab$ times as many ways as choosing $a$ items from the original $n$ items, or exactly the same number of ways as choosing $a$ items from $n$ and then choosing $a - b$ items (or $b$ items) from $a$.

So we have discovered a combinatorial proof of the following identity:

$$ \binom n{a-b} \binom{n-(a-b)}b = \binom na \binom a{a-b} = \binom na \binom ab. $$

If we set $k = a$ and $r = (a - b),$ it should be clear that this is the same identity that is proved in Proving an identity with a combinatorial proof: $\binom{n}{k}\binom{k}{r}=\binom{n}{r}\binom{n-r}{k-r}$.

Answer 2

Expanding out the two quantities, we obtain \begin{align*} &\binom{n}{a} = \frac{n!}{a!(n-a)!} \\ \end{align*} and \begin{align*} &\binom{n}{a-b}\binom{n-(a-b)}{b} \\ &= \frac{n!}{(a-b)!(n-(a-b))!} \frac{(n-(a-b))!}{b! (n-a)!} \\ &= \frac{n!}{(a-b)! b! (n-a)!} \\ &= \binom{n}{a-b,b,n-a} \end{align*}

Since $a!$ isn't generally the same as $(a-b)!b!$, the two quantities aren't equal

Answer 3

Perhaps the error in your reasoning becomes clear if you consider the following collections, given some set $X$ containing $n$ objects.

$X_1$ = All possible subsets containing $a$ objects in $X$.

$X_2$ = All possible pairs of sets $(A,B)$ where $A$ is a subset containing $a - b$ objects in $X$ and $B$ is a subset containing $b$ objects, such that $A$ and $B$ are disjoint.

$X_1$ contains $\binom{n}{a}$ elements. and $X_2$ should contain $\binom{n}{a - b} \binom{n - (a - b)}{b}$ elements.

Let's say the set of objects is $\{1, 2, 3, 4, 5, 6\}$, and $a = 3, b = 1$. $X_2$ will contain $(\{1, 4\}, \{2\})$, $(\{1, 2\}, \{4\})$ and $(\{2, 4\}, \{1\})$ as different pairs. However, $X_1$ counts only one choice using the same numbers: $\{1, 2, 4\}$. So you can see that $X_2$ generally contains more elements than $X_1$.

Thought-provoking question btw.