Permutations and Combinations

The counting principle

A restaurant offers $3$ appetizers, $5$ main courses and $2$ desserts. How many three-course meals are possible?

Every appetizer can pair with every main course, and each of those pairs with every dessert:

$$3 \times 5 \times 2 = 30$$

That is the fundamental counting principle: when choices are made in steps, the total number of outcomes is the product of the number of choices at each step.

It works because each choice branches the ones before it. A tree diagram with $3$ branches, then $5$ from each, then $2$ from each, ends in $30$ leaves.

Factorials: arranging everything

In how many orders can $5$ books stand on a shelf?

The first spot has $5$ choices, the next $4$, then $3$, $2$ and $1$:

$$5 \times 4 \times 3 \times 2 \times 1 = 120$$

That product is written $5!$ and read “five factorial”.

$$n! = n \times (n - 1) \times \dots \times 2 \times 1$$

By definition $0! = 1$ — there is exactly one way to arrange nothing, and the definition makes every formula below work at the edges.

Permutations: order matters

A club of $8$ members elects a president, a vice president and a treasurer. How many results are possible?

Order matters: Ana as president and Ben as treasurer is different from the reverse. Choose one role at a time:

$$8 \times 7 \times 6 = 336$$

This is a permutation — an arrangement of $3$ items chosen from $8$. The general count is

$${}_{n}P_{r} = n \times (n-1) \times \dots \times (n - r + 1) = \frac{n!}{(n - r)!}$$

The factorial form looks longer but says the same thing: start with all $n!$ arrangements, and divide away the $(n - r)!$ orderings of the people not chosen, which do not matter.

Why a combination divides by r!

The same club instead picks a committee of $3$, with no roles. How many committees are possible?

Now Ana, Ben and Cal form one committee, however they are listed. The $336$ permutations count every committee several times — once for each way to order its three members, and $3$ people can be ordered in $3! = 6$ ways.

$$\frac{336}{6} = 56$$

That is a combination:

$${}_{n}C_{r} = \binom{n}{r} = \frac{n!}{r!\,(n - r)!}$$

A combination is a permutation with the reorderings divided out. Every group of $r$ appears $r!$ times among the permutations, so dividing by $r!$ leaves each group counted once.

Deciding which to use

Swap two of the chosen items and ask whether the outcome changed.

Situation	Swap two — different outcome?	Use
gold, silver and bronze medals	yes	permutation
a $4$-digit lock code	yes	permutation
a $5$-card poker hand	no	combination
choosing $3$ toppings for a pizza	no	combination
seating $6$ people in a row	yes	permutation

Counting to find probabilities

When outcomes are equally likely:

$$P(\text{event}) = \frac{\text{number of favorable outcomes}}{\text{total number of outcomes}}$$

Counting fills in both numbers.

A committee of $2$ is chosen at random from $4$ girls and $6$ boys. Find the probability both are girls.

$$\text{total} = \binom{10}{2} = 45 \qquad \text{favorable} = \binom{4}{2} = 6$$ $$P(\text{both girls}) = \frac{6}{45} = \frac{2}{15}$$

The same answer comes from the multiplication rule: $\tfrac{4}{10} \times \tfrac{3}{9} = \tfrac{12}{90} = \tfrac{2}{15}$. Two methods agreeing is a strong check, and whichever is shorter for a given problem is the one to use.

Worked examples

Common mistakes

Practice problems