Combinations: Selecting $k$ elements from a set of $n$.

If we have a group of $n$ individuals and we plan to select $k$ of them, how many ways are there to do this? We denote this number $\binom{n}{k}$ and express it verbally as “n choose k”.

The collection of quantities $\binom{n}{k}$ has many names, but they are most famous called the binomial coefficients. In the context of counting ways to select individuals from a group, $\binom{n}{k}$ is commonly called the number of combinations and is also written $_nC_k$. This name is held in contrast to the number of permutations $_nP_k$, which is the number of ways to select $k$ individuals from a set of size $n$ when the order of selection matters.

The binomial coefficient formula (or combinations formula) is given as follows:

$$ \displaystyle\binom{n}{k} = \frac{n!}{k!(n-k)!} $$

where $n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$. The number $n!$ is verbally expressed “n factorial.”

Derivation of the binomial coefficient formula

There are three steps to understand this formula.

1. We observe that $n!$ is the number of ways that a set of $n$ individuals can be rearranged if their order matters.
2. If we are only interested in selected $k$ individuals, but the order of selection still matters, then we need to divide by all possible ways to leave out $(n - k)$ individuals. This yields the permuation formula: $\displaystyle _nP_k = \frac{n!}{(n-k)!}$.
3. Now we need to divide out all the rearrangements of the $k$ selected individuals. Since there are $k!$ ways to do this, $k!$ is put in the denominator of the permutation formula and we attain the combinations formula.

When there is over-counting, why do we divide by these factors $(n-k)!$ and $k!$? The easiest way to see this is to look at an example where all of the options are written in a tabular format.

TMM_Combinations.pdf

Why do we multiply two binomial coefficients when there are two groups?

TMM_Count_Multiply.pdf