I was looking for derivations for formulas of permutations and combinations and I have found this page. The page starts the derivation of combinations formula (the last section of the page) with the following:
To derive a formula for C(n, k), separate the issue of the order in
which the items are chosen, from the issue of which items are chosen,
as follows.The number of permutations of k items taken from n items is
( number of sets
of k items taken from n ) × ( number of ways to order the k items ).
Yes, it is intuitive but how do we really know that this is indeed the case? In other words, can we rigorously show that
The number of permutations of k items taken from n items is
( number of sets
of k items taken from n ) × ( number of ways to order the k items ).
?
Best Answer
Note that what you have written in words is the expression: $\binom{n}{k} k!$. (Since $\binom{n}{k} = \frac{n!}{(n-k)!k!}$ is the number of ways to choose $k$ objects from a collection of $n$ objects, and $k!$ is the number of ways to order $k$ objects). We could rewrite this as $$\binom{n}{k} k! = n(n-1)\dots(n-k+1).$$ Using induction on $k$, you can show that this is the right number.
Additional notes:
Their idea is pretty intuitive, but making their idea of "separating the issues" rigorous is much less straightforward than just noting that ordering a $k$ subset of $n$ objects is the same thing as just ordering them in the order that you pick them out. So there are $n$ choices of your first object, $n-1$ choices of your second object, and so on... We can make this rigorous using induction. Assume that the above formula holds for choosing $k-1$ objects. Then to choose $k$ objects, first choose $k-1$ objects. We know by induction that there are $n(n-1)\dots(n-k+2)$ ways of doing so. Now we must choose the last object. There are $n-(k-1) = n-k+1$ objects left. And so the number of ways of choosing the $k$ objects with an ordering is $n(n-1)\dots(n-k+2)(n-k+1)$. By induction the formula holds for all $k$.
So we can see that what they had is correct by rephrasing the problem into something that is easier to see inductively.