# 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)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:

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

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$ |