Math Core

Listing every outcome works for two dice. It does not work for dealing a $5$ -card hand, where there are over $2.5$ million possibilities. To find probabilities in big sample spaces, you need to count without listing. This lesson gives you three tools: the fundamental counting principle, permutations and combinations.

The fundamental counting principle

Fundamental counting principle

If one choice can be made in $m$ ways and a second choice can then be made in $n$ ways, the two choices together can be made in $m \cdot n$ ways. This extends to any number of choices: multiply the number of options at each step.

You've already used this: two number cubes give $6 \cdot 6 = 36$ outcomes.

Worked example: Codes

A locker code is $3$ letters followed by $2$ digits, and letters and digits may repeat. How many codes are possible?

There are $26$ choices for each letter and $10$ for each digit:

26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 = 1{,}757{,}600.

Factorials and arrangements

How many ways can $5$ books be lined up on a shelf? There are $5$ choices for the first spot, then $4$ left for the second, then $3$ , $2$ and $1$ :

5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120.

This product has a name.

Definition

Factorial

For a positive integer $n$ , $n$ factorial is $n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$ . By definition, $0! = 1$ . There are $n!$ ways to arrange $n$ different objects in a row.

Permutations: order matters

Now suppose only some of the objects are used. A club of $10$ members elects a president, a vice president and a secretary. There are $10$ choices for president, then $9$ for vice president, then $8$ for secretary: $10 \cdot 9 \cdot 8 = 720$ ways. Each result is a permutation, an arrangement in which order (here, which office) matters. Electing Ana president and Ben secretary is different from the reverse.

Permutations

The number of permutations of $n$ objects taken $r$ at a time is

{}_nP_r = \frac{n!}{(n-r)!} = n(n-1)(n-2)\cdots(n-r+1).

That last form is $r$ factors, counting down from $n$ .

Check with the club: ${}_{10}P_3 = \dfrac{10!}{7!} = 10 \cdot 9 \cdot 8 = 720$ . The $7!$ cancels the part of $10!$ you don't use.

Combinations: order doesn't matter

Now the club picks a committee of $3$ with no titles. The committee {Ana, Ben, Cy} is the same committee however you list the names. The $720$ permutations count each committee several times, once for each of the $3! = 6$ ways to order its members. So the number of committees is

\frac{720}{6} = 120.

A selection in which order doesn't matter is a combination.

Combinations

The number of combinations of $n$ objects taken $r$ at a time is

{}_nC_r = \frac{{}_nP_r}{r!} = \frac{n!}{r!\,(n-r)!}.

It is also written $\dbinom{n}{r}$ and read " $n$ choose $r$ ."

Common mistake

Before you use a formula, ask: if I swap two of the chosen items, is it a different result? If yes (offices, finishing places, a code, a seating order), use permutations. If no (a committee, a hand of cards, pizza toppings), use combinations. Using ${}_nP_r$ for a committee overcounts by a factor of $r!$ .

Worked example: Permutation or combination?

In how many ways can gold, silver and bronze medals be awarded to $3$ of $8$ runners?
In how many ways can a coach choose $3$ of $8$ runners for a relay pool, with no order?
Medals are different, so order matters: ${}_8P_3 = 8 \cdot 7 \cdot 6 = 336$ .
A group without roles, so order doesn't matter: ${}_8C_3 = \dfrac{336}{3!} = \dfrac{336}{6} = 56$ .

Counting to find probabilities

When outcomes are equally likely, $P(\text{event}) = \dfrac{\text{favorable outcomes}}{\text{total outcomes}}$ , and now you can count both with combinations or permutations.

Worked example: Choosing a committee at random

A committee of $3$ is chosen at random from $5$ girls and $4$ boys. What is the probability that the committee is all girls? What is the probability that it has exactly $2$ girls?

Total committees: ${}_9C_3 = \dfrac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 84$ .

All girls: choose $3$ of the $5$ girls: ${}_5C_3 = 10$ .

P(\text{all girls}) = \frac{10}{84} = \frac{5}{42}.

Exactly $2$ girls: choose $2$ of $5$ girls and $1$ of $4$ boys. By the counting principle, that's ${}_5C_2 \cdot {}_4C_1 = 10 \cdot 4 = 40$ committees.

P(\text{exactly 2 girls}) = \frac{40}{84} = \frac{10}{21}.

Tip

${}_nC_r = {}_nC_{n-r}$ . Choosing $3$ people to be on a committee from $10$ is the same as choosing $7$ to leave off, so ${}_{10}C_3 = {}_{10}C_7 = 120$ . Use whichever is quicker to compute.