Combinations of Elements in Sets

Recall from the Permutations of Elements in Sets page that if $A$ is a finite $n$-element set and if $0 \leq k \leq n$ then a $k$-permutation is an ordered arrangement of $k$ of those $n$ elements.

For example, suppose that we have the set $A = \{ x, y, z \}$. We saw in a similar example that there are exactly $6$, $2$-permutations, namely we have $(x, y), (x, z), (y, x), (y, z), (z, x)$ and $(z, y)$. Now let's look at a similar problem - determining how many subsets of $A$ have two elements in them. In this case, we could say $\{ x, y \}, \{ x, z \}, \{ y, z \}, \{ y, z \}, \{ z, x \}$ and $\{ z, y \}$ like before - but we'd be wrong because we the order of elements in a set does not matter. In fact, there are only three subsets of $A$ with two elements, namely $\{ x, y \}, \{ x, z\}$ and $\{ y, z \}$. This gives us motivation for our next definition.

Definition: A $k$-Combination is a selection of $k$ elements from a finite $n$-element set $A$.

When the context is clear, it is usually preferred to just say "combination" as opposed to "$k$-combination". Furthermore, we must have that $0 \leq k \leq n$.

Note that the definitions of a permutation and a combination are similar, however, a combination is simply a selection of $k$ elements without any care towards order. For example, consider a set $A$ of pizza toppings: ham, pepperoni, mushrooms, and spinach:

(1)

\begin{align} \quad A = \{ h, p, m, s \} \end{align}

Now suppose that we want to determine how many different pizzas we can create. Clearly, the order of which we put the toppings on does not really affect the final result of the pizza, so our question of determining how many different pizzas we can create turns out to be finding how many different subsets with $0$, $1$, $2$, $3$, and $4$ elements we can create.

The simplest subset of $A$ is the empty set $\emptyset$ representing a plain pizza. The subsets of $A$ containing only one element are $\{ h \}, \{ p \}, \{ m \}$ and $\{ s \}$ which represent single-topping pizzas. The subsets of $A$ containing two elements are $\{ h, p \}, \{ h, m \}, \{ h, s \}, \{ p, m\} , \{ p, s \}, \{ m, s \}$ represent the two-topping pizzas. The subsets of $A$ containing three elements are $\{ h, p, m \}, \{ h, p, s \}, \{ h, m, s \}$, and $\{p, m, s \}$ represent the three-topping pizzas. Lastly, the subset of $A$ containing four elements is the whole set, that is $\{h, p, m, s \}$ which is a pizza containing all available toppings. The diagram below lists all of the possible pizza topping combinations:

So there is one $0$-combination, four $1$-combination, six $2$-combinations, four $3$-combinations, and one $4$-combinations. It is often times useful to know the total number of $k$-combinations from an $n$-element set, and the following theorem gives us a way to determine that number.

Theorem 1: If $A$ is an $n$-element set then the number of $k$-combinations from $A$ is given by $\binom{n}{k} = \frac{1}{k!} \cdot P(n, k) = \frac{n!}{k! (n - k)!}$.

The notations "$C(n, k)$" and "$_n C_k$" are also used to mean the same thing as "$\binom{n}{k}$", but they are much less frequently used. Regardless, all of this notation should be read as "$n$ choose $k$". Furthermore, by convention we will have that $\binom{0}{0} = 1$, $\binom{0}{k} = 0$, and if $n < k$, $\binom{n}{k} = 0$. The numbers $\binom{n}{k}$ are commonly referred to as Binomial Coefficients. We will look more into these important numbers soon.

• Proof: Fix $n$ as a positive integer and let $A = \{ x_1, x_2, ..., x_n \}$. For $0 \leq k \leq n$ we will let $\binom{n}{k}$ represent the total number of $k$-combinations from $A$. The number of ways that we can arrange these $k$ elements after they've been selected from $A$ is $k!$, and so by the multiplication principle, the total number of $k$-permutations is given by:

(2)

\begin{align} \quad P(n, k) = \binom{n}{k} \cdot k! \end{align}

• Since $k! \neq 0$ for each $k = 0, 1, 2, ..., n$ we can divide both sides by $k!$ to get what we desire:

(3)

\begin{align} \quad \binom{n}{k} = \frac{1}{k!} \cdot P(n, k) = \frac{n!}{k! (n - k)!} \quad \blacksquare \end{align}

You should verify that Theorem 1 indeed holds for the pizza example given above. Below is a table of some values of $\binom{n}{k}$ for small $n$ and $0 \leq k \leq n$:

$\binom{0}{0} = 1$
$\binom{1}{0} = 1$	$\binom{1}{1} = 1$
$\binom{2}{0} = 1$	$\binom{2}{1} = 2$	$\binom{2}{2} = 1$
$\binom{3}{0} = 1$	$\binom{3}{1} = 3$	$\binom{3}{2} = 3$	$\binom{3}{3} = 1$
$\binom{4}{0} = 1$	$\binom{4}{1} = 4$	$\binom{4}{2} = 6$	$\binom{4}{3} = 4$	$\binom{4}{4} = 1$
$\binom{5}{0} = 1$	$\binom{5}{1} = 5$	$\binom{5}{2} = 10$	$\binom{5}{3} = 10$	$\binom{5}{4} = 5$	$\binom{5}{5} = 1$