Lesson 8

In the general case, \({n \choose k}\) denotes the number of \(k\)-element subsets (also called combinations) in an \(n\)-element set. We have already derived the formula for it: \[\binom{n}{k}=\frac{n!}{k!(n-k)!}\ .\] Let's repeat the reasoning once more. There are \(n\) ways to choose the first element, \((n-1)\) the second, and so on. In total, there are \(n(n-1)\dotsb(n-k+1)=\frac{n!}{(n-k)!}\) ways to choose \(k\) elements. However, in this way, we count \(k\)-permutations (or \(k\)-arrangements), not \(k\)-element subsets. Each subset in this process is counted \(k!\) times. Thus, we need to divide \(\frac{n!}{(n-k)!}\) by \(k!\).

There is another way to derive this formula. To count all \(k\)-element subsets, consider all \(n!\) permutations and take the first \(k\) elements from each. Naturally, each subset \(A\) of size \(k\) will be counted multiple times: the elements of \(A\) can appear in any order in the permutation (a total of \(k!\) ways), and the remaining elements can also be in any order (\((n-k)!\) ways).