What is wrong with the following "proof" that ${{n}\choose{r}}={{n}\choose{k}}\cdot{{n-k}\choose{r-k}}$ where $k<r$?
- Each possible combination can be divided into two disjoint sets, the first having $k$ elements and the second having $r-k$ elements.
- For the first set, we can choose any of the $n$ total elements to choose from in any order, and we pick exactly $k$ of these hence the number of possibilities is ${n}\choose{k}$.
- For the second set, we need to pick $r-k$ objects in any order, but we can't repeat any used in the first set which means there are only $n-k$ objects left to choose from. Hence the number of possibilities is ${n-k}\choose{r-k}$.
- Every option for the first set can be paired with every other option for the second, so there are ${{n}\choose{k}}\cdot{{n-k}\choose{r-k}}$ total ways to choose $r$ objects from a set of $n$.
But this is clearly false, as ${{10}\choose{5}}\neq{{10}\choose{3}}\cdot{{7}\choose{2}}$. What went wrong?
Consider the subset $\{1,2,3,4,5\}$ of $\{1,2,3,\cdots,10\}$.
Your procedure could construct it from $\{1,2,3\}$ and $\{4,5\}$, but it could have also constructed it from many different pairs of subsets like $\{3,4,5\}$ and $\{1,2\}$ instead. Since your product of binomials counts these all separately, it is vastly overcounting.
In fact, the factor by which it is overcounting is how many ways there are to split an $r$-subset into a $k$-subset and an $(r-k)$-subset, which is $\binom{r}{k}$. Therefore $\binom{n}{r}=\binom{n}{k}\binom{n-k}{r-k}/\binom{r}{k}$.