Choose

Choosing from a set of four

Suppose you have four children,

\[ S = \left\{ \textrm{John}, \textrm{Thomas}, \textrm{Meg}, \textrm{James} \right\}. \]

Your motorcycle can carry only one passenger. Obviously, you can take John, Thomas, Meg, or James as your passenger. There are four possible “combinations” of one choice given a set of four.

\[ \textrm{One-Element Subsets of } S = \left\{ \left\{ \textrm{John} \right\}, \left\{ \textrm{Thomas} \right\}, \left\{ \textrm{Meg} \right\}, \left\{ \textrm{James} \right\} \right\} \]

You add a sidecar to your bike. Now you can take two passengers! You can take John and Thomas, John and Meg, John and James, Thomas and Meg, Thomas and James, or Meg and James. There are six possible combinations of two choices given a set of four.

\[ \textrm{Two-Element Subsets of } S = \left\{ \left\{ \textrm{John}, \textrm{Thomas} \right\}, \left\{ \textrm{John}, \textrm{Meg} \right\}, \left\{ \textrm{John}, \textrm{James} \right\}, \left\{ \textrm{Thomas}, \textrm{Meg} \right\}, \left\{ \textrm{Thomas}, \textrm{James} \right\}, \left\{ \textrm{Meg}, \textrm{James} \right\} \right\} \]

You upgrade your life to a very small hatchback. You’d think you can squeeze one in the front and three in the back, but no. The hatchback gives you only three passengers. You can take John, Thomas, and Meg; John, Thomas, and James; John, Meg, and James; or Thomas, Meg, and James. There are four possible combinations of three choices given a set of four.

\[ \textrm{Three-Element Subsets of } S = \left\{ \left\{ \textrm{John}, \textrm{Thomas}, \textrm{Meg} \right\}, \left\{ \textrm{John}, \textrm{Thomas}, \textrm{James} \right\}, \left\{ \textrm{John}, \textrm{Meg}, \textrm{James} \right\}, \left\{ \textrm{Thomas}, \textrm{Meg}, \textrm{James} \right\} \right\} \]

You invest in a van. Now you can fit all four children. The order in which you choose your four passengers does not matter. There is, of course, only one way to choose all four from four.

\[ \textrm{Four-Element Subsets of } S = \left\{ \left\{ \textrm{John}, \textrm{Thomas}, \textrm{Meg}, \textrm{James} \right\} \right\} \]

You crash the van and are stuck with a bicycle. Now you have a passenger capacity of zero. We define that there is one way to choose zero from four, which could be represented as an empty set, \(\emptyset = \{ \}\).

\[ \textrm{Zero-Element Subsets of } S = \left\{ \left\{ \right\} \right\} \]

Note that \(\left\{\left\{\right\}\right\} \ne \left\{\right\}\). The cardinality (size) of the set containing the empty set is 1.

The Combination Formula

In higher mathematics, the word “choose” is interchangeable with the combination formula. The combination formula counts the number of subsets of size \(r\) that can be constructed from a set of size \(n\). Two stacked numbers, surrounded by large parentheses, is one of many common notations for the combination formula. The top number is the size \(n\) of the set you are choosing from, and the bottom number \(r\) is the amount you are choosing.

\[ { n \choose r } = {}_n C_r = \frac{n!}{r! (n-r)!} \]

When read aloud, \(n \choose r\) is spoken “\(n\) choose \(r\).” \({}_n C_r\) is generally read “\(n\) combinations taken \(r\) at a time.” The definition uses the factorial function. The factorial of a non-negative integer \(n\) is the product of all integers from \(n\) to \(1\).

\[ n! = n \times (n-1) \times (n-2) \times \dots 3 \times 2 \times 1 = \prod_{i=1}^{n}{i} \]

The factorial of zero is defined as \(0! = 1\). The intuition for this is the bicycle: there is only one way you can take zero passengers on your bike.

Derivation

To derive the combination formula, we should first define and derive the permutation formula. The number of permutations differs from combinations in that order matters. In the strict mathematical sense, a set is unordered, so

\[ \{ a, b, c \} = \{ c, b, a \}. \]

Counting the number of possible permutations from a set of size \(n\) is easy. First, you have \(n\) possibilities. Select one and now you have \(n-1\) possibilities. Select another and now you have \(n-2\) possbilities. Continue until you have selected as many elements as you want from your set.

\[ {}_n P_r = n \times (n-1) \times (n-2) \times \dots \times (n-r) = \frac{n!}{(n-r)!} \]

The identity on the right is the standard definition provided in any discrete mathematics textbook. The \((n-r)!\) in the denominator is a clever way to remove terms of \(n!\) from the numerator. Clever…but not obvious. When in doubt with a combinatoric problem, just write all of the possibilities out (or program a computer to write them for you).

If you want all permutations that can be made from a set of size \(n\), then this is just

\[ {}_n P_n = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n! \]

This should be very intuitive. How many ways can you order \(S = \{ a, b, c, d, e \}\)? You begin with five options in the first element, then four, three, two, and finally have only one element remaining at the end.

Now that we have the permutation formula, we can derive the combination formula. The combination formula is just the permutation formula without duplicate orderings. Again, the combination formula counts the number of unordered subsets.

When choosing \(r\) elements from a set of size \(n\), we first have \(n\) possibilities to choose. Next, we have \(n-2\). Then, \(n-3\), and so on. We take the product, and now divide by the number of orderings that could be made from \(r\) elements. How many orderings of \(r\) elements are possible? We use the permutation formula to find out. \(r\) elements can be ordered in \({}_r P_r = r!\) ways.

\[ {}_n C_r = {n \choose r} = \frac{{}_n P_r}{{}_r P_r} = \frac{n!/(n-r)!}{r!} = \frac{n!}{r!(n-r)!} \]

We could also have defined the permutation formula in terms of the combination formula. First, we would have found all the size \(r\) subsets of our set of size \(n\). Next, we would multiply this count by the number of ways you can arrange (permute) \(r\) items, which is just \(r! = r \times (r-1) \times (r-2) \times \dots \times 3 \times 2 \times 1\).

\[ {}_n P_r = r! {n \choose r} = r! \frac{n!}{r! (n - r)!} = \frac{n!}{(n-r)!} \]

Choosing Two

It is very useful to work through \(n \choose 2\). Counting the number of pairs that can be chosen from a set is a common application. For this, I will use the choose function in the R language.

choose(0:20, 2)

 [1]   0   0   1   3   6  10  15  21  28  36  45  55  66  78  91 105 120 136 153 171 190

We see that \({0 \choose 2} = {1 \choose 2} = 0\), which makes sense because we cannot choose 2 elements from an empty set or a set of one element.

The rest of these are the familiar triangular numbers. You may have seen the statement

\[ {n \choose 2} = \frac{n!}{2! (n-2)!} = \frac{n \times (n-1) \times (n-2) \times (n-3) \times \dots \times 3 \times 2 \times 1}{2 \times (n-2) \times (n-3) \times \dots 3 \times 2 \times 1} = \frac{n(n-1)}{2} = \frac{n^2 - n}{2} \]

This equation can be used to count the number of pair-wise combinations of any set.

The intuition for the identity \(n(n-1)/2\) is that each element can be paired with each other element, but not itself, and we half the count because set order does not matter.

The Curse of Combinatorics

The number of possible arrangements from choosing two from a set becomes very huge, very quickly. The explosive growth of combinations is sometimes called “the curse of combinatorics.” Combinatorial problems can be challenging to analyze due to their explosive complexity, where the difficulty of a problem is proportionate to the factorial or exponent of the set size.

For example, suppose your company needed to assemble a project team of 10 from a pool of 100 employees. How many possible teams could be created? One might lazily guess 10, or perhaps 1000, but the answer is much larger.

choose(100, 10)

[1] 1.731031e+13

There are more than 17 trillion teams of 10 that could be assembled from 100 employees.

Pascal’s Formula and Pascal’s Triangle

Pascal’s Formula is an alternative representation of the combination formula. I prefer this definition, but it requires more understanding of recursion.

\[ {n \choose r} = \frac{n!}{r! (n-r)!} = {n - 1 \choose r - 1} + {n - 1 \choose r} \]

The idea is that you scan the set from left to right. You will either choose an element or not. If you have not chosen the element, then you still need to choose \(r\) from a subset of size \(n-1\). If you did choose the element, then you need only \(r-1\) from the subset of \(n-1\).

This idea of selecting or not selecting an element helps us to establish how many possible combinations of combinations there are. Returning to the children example, you can choose or not choose John, choose or not choose Thomas, choose or not choose Meg, and choose or not choose James.

2 * 2 * 2 * 2

[1] 16

There are 16 possible combinations from a set of size four.

choose(4, 0:4)

[1] 1 4 6 4 1

sum(choose(4, 0:4))

[1] 16

In general, there are \(2^n\) subsets of any set of size \(n\).

Pascal also gave us Pascal’s triangle. Pascal’s triangle is usually shown centered, but here are the first few rows:

for (i in 0:15) {
  print(choose(i, 0:i))
}

[1] 1
[1] 1 1
[1] 1 2 1
[1] 1 3 3 1
[1] 1 4 6 4 1
[1]  1  5 10 10  5  1
[1]  1  6 15 20 15  6  1
[1]  1  7 21 35 35 21  7  1
[1]  1  8 28 56 70 56 28  8  1
 [1]   1   9  36  84 126 126  84  36   9   1
 [1]   1  10  45 120 210 252 210 120  45  10   1
 [1]   1  11  55 165 330 462 462 330 165  55  11   1
 [1]   1  12  66 220 495 792 924 792 495 220  66  12   1
 [1]    1   13   78  286  715 1287 1716 1716 1287  715  286   78   13    1
 [1]    1   14   91  364 1001 2002 3003 3432 3003 2002 1001  364   91   14    1
 [1]    1   15  105  455 1365 3003 5005 6435 6435 5005 3003 1365  455  105   15    1

The first number in each row corresponds to \({n \choose 0} = 1\) (there is one way to choose none). The second number in each row corresponds to \({n \choose 1} = n\) (there are \(n\) ways to choose 1 from \(n\)). The third number in each row are the triangular numbers, \(n \choose 2\).

Each number in the triangle is the sum of the two numbers above it (if it were centered correctly). For example, \(1365 = 364 + 1001\). This property is due to Pascal’s Formula.