7.2 Permutations and combinations

Choosing people for ranked positions differs from choosing a group. In the first task, swapping two people changes the outcome; in the second, it does not. Permutations and combinations encode that single distinction and save you from listing every arrangement.

This is intermediate counting. Begin with OpenStax's permutation examples and then its combination examples. Module 7.1 counted successive choices by multiplying; here we decide when different orders of those choices represent the same outcome.

A basic idea: does swapping count?

Selecting Ari and Bela for first and second place gives two possibilities: Ari first or Bela first. Selecting Ari and Bela for a two-person team gives just one team. The people are the same; the meaning of the outcome determines the count.

A quick tour of formulas

The number of ways to arrange $n$ distinct objects in a row is $n!=n(n-1)\cdots2\cdot1$, with $0!=1$ by convention. If $r$ of them ($0\le r\le n$) are chosen in order, without replacement,

$$P(n,r)=n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!}.$$

If only the chosen set matters, each set of $r$ objects appears in $r!$ different orders above. Divide those repeats away:

$$\binom{n}{r}=\frac{P(n,r)}{r!} =\frac{n!}{r!(n-r)!},\qquad 0\le r\le n.$$

The symmetry $\binom{n}{r}=\binom{n}{n-r}$ says choosing $r$ objects is equivalent to choosing which $n-r$ are left out. These formulas assume distinct objects and no replacement. Repetition or extra restrictions require a new count.

Application 1: medal positions

Six runners finish a race. How many possible ordered gold, silver, and bronze results are there if ties are impossible?

1. Identify ordered roles. Gold and silver swapped is a different result, so use a permutation.
2. Count stage by stage. There are $6$ choices for gold, $5$ remaining for silver, and $4$ for bronze.
3. Multiply. $P(6,3)=6\cdot5\cdot4=120$.

The factorial formula gives the same result: $6!/3!=120$.

Application 2: selecting features

A small model has $8$ distinct candidate features. How many groups of $3$ features can be selected if their order in a list has no meaning?

1. Count ordered picks first. $P(8,3)=8\cdot7\cdot6=336$.
2. Remove duplicate orderings. Each selected group appears in $3!=6$ orders.
3. Divide. $\binom{8}{3}=336/6=56$ groups.

The calculation says nothing about which group is best for the model. It only counts the possible choices.