Skip to main content

Section 3.4 Combinations

When counting various outcomes sometimes the order of things does not matter. If so, each unique unordered outcome is called a combination.

Once again, consider the permutations when selecting three letters from {A, B, C, D}.

    • A,B,C
    • A,C,B
    • B,A,C
    • B,C,A
    • C,A,B
    • C,B,A
    • A,B,D
    • A,D,B
    • B,A,D
    • B,D,A
    • D,A,B
    • D,B,A
    • A,C,D
    • A,D,C
    • C,A,D
    • C,D,A
    • D,A,C
    • D,C,A
    • B,C,D
    • B,D,C
    • C,B,D
    • C,D,B
    • D,B,C
    • D,C,B

Notice how these 24 permutations fall into only four distinct categories if the order does not matter. Therefore, from a group of size four you can pick an unordered subset of size three in only 4 ways rather than the original 24.

In general, it would be nice to have a direct formula to determine the number of such combinations without having to explicitly list them all out.

Consider creating a permutation of r objects from a set of size n by first picking an unordered subset of size r and then counting the number of ways to order that subset. Using our notation and the multiplication principle,

\begin{equation*} _nP_r = _nC_r \cdot r! \end{equation*}

Dividing by \(r!\) gives the result.

Label each item in your group in some defined order. Since order doesn't matter, as you repeatedly sample r times with replacement you can always write down your outcomes sorted from low to high placement. Finally, separate like values by some symbol, say "|", and consider each of the n distinct objects as indistinct *'s. There will be n-1 of these separators since there will be n to choose from. For example, if choosing r=6 times from the set {a, b, c, d}, then the outcome b, b, a, d, a, b could be collected as a, a, b, b, b, d and written in our code as **|***||* . Notice that shuffling around the identical *'s would not change the code (and similarly for the identical |'s) but swapping a * with a | would be a different outcome. Therefore, we can consider this to be a multinomial coefficient and the number of ways to rearrange this code is

\begin{equation*} \frac{(r + n-1)!}{r!(n-1)!}. \end{equation*}

Let's apply the this new Combination forumula.

Notice that to determine the number of outcomes required you to use the combination forumula several times and then multiply the results using the multiplication principle.

Use the new Combination formula again.

Once again, you can see that using the formulas can be easy and also can be part of a bigger problem pasted together using the multiplication principle.

Revisiting your ipad's security, what happens if the order in which the digits are entered does not matter? If so, then you would be picking a combination of 4 digits without replacement from a group of 10 digits. Namely,

\begin{align*} \frac{10!}{4!6!} & = \frac{10 \times 9 \times 8 \times 7 \times 6!}{4 \times 3 \times 2 \times 1 \times 6!}\\ & = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1}\\ & = \frac{5040}{24}\\ & = 210. \end{align*}

Notice that the total number of options is much smaller when order does not matter.

Note that if you were allowed to reuse the digits then the number of possible outcomes would be

\begin{align*} \frac{13!}{4!9!} & = \frac{13 \times 12 \times 11 \times 10}{4 \times 3 \times 2 \times 1} \\ & = 715 \end{align*}

which once again is more since numbers are allowed to repeat.

Definition 3.4.6 Binomial Coefficients

The value \(_nC_r\) is known as the binomial coefficient. It is denoted by \({n \choose r}\) and is read "n choose k".

Binomial coefficients have a number of interesting properties. Many of these are very useful as well in probability calculations. Several of these properties are collected below. In particular, these relationships verify that the binomial coefficients are the values found in Pascal's Triangle.

  1. \(\binom{n}{0} = \frac{n!}{0!(n-0)!} = 1\)
  2. \(\binom{n}{n} = \frac{n!}{n!(n-n)!} = 1\)
  3. \(\binom{n}{1} = \frac{n!}{1!(n-1)!} = n\)
  4. \(\binom{n}{n-1} = \frac{n!}{(n-1)!(n-(n-1))!} = n\)
  5. \(\binom{n}{r} = \frac{n!}{r!(n-r)!} = \frac{n!}{(n-r)!(n-(n-r))!} = \binom{n}{n-r}\)
  6. \begin{align*} \binom{n}{r} + \binom{n}{r+1} & = \frac{n!}{r!(n-r)!} + \frac{n!}{(r+1)!(n-(r+1))!}\\ & = (r+1) \frac{n!}{(r+1)!(n-r)!} // + (n-r) \frac{n!}{(r+1)!(n-r))!}\\ & = \frac{(r+1) n! + (n-r)n!}{(r+1)!(n-r)!}\\ & = \frac{(n+1) n!}{(r+1)!((n+1)-(r+1))!}\\ & = \binom{n+1}{r+1} \end{align*}