Math Core

How many different license plates can a state issue? How many ways can a club pick officers, or a coach pick a starting lineup? Listing every possibility quickly becomes hopeless, but a few counting principles answer these questions with a single calculation. They are also the foundation of probability.

The multiplication and addition principles

Fundamental counting principles

Multiplication principle. If a task is done in a sequence of steps, with $m_1$ ways to do the first step, $m_2$ ways to do the second step (no matter how the first was done), and so on, then the whole task can be done in $m_1 \cdot m_2 \cdots m_k$ ways.

Addition principle. If a task can be done in one of several non-overlapping cases, count each case separately and add.

Use "and then" as a signal to multiply, and "either … or" (with cases that can't both happen) as a signal to add.

Worked example: License plates

A plate has 3 letters followed by 4 digits. Letters and digits may repeat. How many plates are possible? How many if no letter and no digit repeats?

With repetition allowed, each letter slot has $26$ choices and each digit slot has $10$ :

26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 26^3 \cdot 10^4 = 175{,}760{,}000.

Without repetition, each slot has one fewer choice than the slot before it of the same kind:

26 \cdot 25 \cdot 24 \cdot 10 \cdot 9 \cdot 8 \cdot 7 = 15600 \cdot 5040 = 78{,}624{,}000.

Permutations: order matters

Arranging $n$ different objects in a row uses the multiplication principle: $n$ choices for the first spot, $n - 1$ for the second, and so on down to $1$ . That's $n!$ arrangements. Six books can be shelved in $6! = 720$ orders.

Often you only fill $r$ of the spots. Filling $r$ ordered positions from $n$ different objects gives $n(n-1)\cdots(n - r + 1)$ ways, a product of $r$ factors.

Definition

Permutation

A permutation of $r$ objects chosen from $n$ is an ordered arrangement of them. The number of such arrangements is

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

Combinations: order doesn't matter

If you pick a committee of 3 from 12 people, the selection $\{\text{Ana}, \text{Ben}, \text{Cy}\}$ is the same committee no matter what order you name them in. Each group of 3 people can be ordered in $3! = 6$ ways, so counting ordered lists overcounts every committee exactly $6$ times.

Definition

Combination

A combination of $r$ objects chosen from $n$ is an unordered selection. The number of combinations is

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

These are the same binomial coefficients as in the last lesson. That's no coincidence: the coefficient of $x^{n-r}y^r$ in $(x+y)^n$ counts the ways to choose which $r$ of the $n$ factors contribute a $y$ .

Worked example: Officers versus a committee

A club has 12 members.

(a) In how many ways can it choose a president, a vice president and a treasurer?

The roles are different, so order matters: ${}_{12}P_3 = 12 \cdot 11 \cdot 10 = 1320$ .

(b) In how many ways can it choose a 3-person planning committee?

The members of a committee have no roles, so order doesn't matter:

\binom{12}{3} = \frac{1320}{3!} = \frac{1320}{6} = 220.

Tip

To decide between a permutation and a combination, swap two of the chosen objects. If that produces a different outcome (different officers, a different finishing order, a different PIN), order matters. If it's the same outcome (the same committee, the same hand of cards, the same pizza toppings), use a combination.

Arrangements with repeated objects

How many different "words" can you make from the letters of LEVEL? If all 5 letters were different, there would be $5!$ arrangements. But swapping the two L's, or the two E's, doesn't change the word, so $5!$ counts each word $2! \cdot 2!$ times. The answer is $\dfrac{5!}{2!\,2!} = 30$ .

Distinguishable arrangements

The number of distinguishable arrangements of $n$ objects, where $n_1$ are alike of one kind, $n_2$ are alike of another kind, and so on, is

\frac{n!}{n_1!\,n_2!\cdots n_k!}.

Worked example: Letters of a word

How many distinguishable arrangements are there of the letters in MISSISSIPPI?

There are $11$ letters: one M, four I's, four S's and two P's.

\frac{11!}{1!\,4!\,4!\,2!} = \frac{39{,}916{,}800}{24 \cdot 24 \cdot 2} = \frac{39{,}916{,}800}{1152} = 34{,}650.

Counting the complement, and counting paths

Problems with "at least one" are usually easiest to do backwards: count everything, then subtract the outcomes you don't want.

Worked example: At least one

A committee of 5 is chosen from 7 women and 6 men. How many committees include at least one man?

All committees: $\dbinom{13}{5} = 1287$ . Committees with no men (all women): $\dbinom{7}{5} = 21$ . So

1287 - 21 = 1266

committees have at least one man.

Common mistake

Don't count "at least one man" as "pick one man, then pick any 4 others": $6 \cdot \dbinom{12}{4} = 2970$ . That counts a committee with two men twice (once for each man you could have "picked first"), and committees with more men even more often. Use the complement, or split into non-overlapping cases (exactly 1 man, exactly 2 men, and so on) and add.

Combinations also count lattice paths. To walk from $(0, 0)$ to $(5, 3)$ on a grid using only unit steps right (R) or up (U), you take $8$ steps, exactly $3$ of which are U. A path is decided by choosing which 3 of the 8 steps go up, so there are $\dbinom{8}{3} = 56$ paths.

One path from A to B: R R U U R R U R. Every shortest path uses 5 right steps and 3 up steps, so there are C(8, 3) = 56 of them.

Practice

Practice 1

You have 4 shirts, 3 pairs of pants and 2 pairs of shoes. How many different outfits (one of each) can you make?