Permutations and Combinations

By the end of this lesson, you will be able to compute permutations and combinations using formulas and factorial notation, distinguish when order matters (permutation) vs. when it doesn't (combination), and apply the Fundamental Counting Principle.

The Big Idea

The central question of counting: how many ways can something happen? The answer depends critically on whether order matters. Permutations count ordered arrangements; combinations count unordered selections. These are the tools underlying all of probability and statistics.

Fundamental Counting Principle

If event A can occur in $m$ ways and event B in $n$ ways, the sequence A then B can occur in $m \times n$ ways.

Example: 4 shirts and 3 pants → $4 \times 3 = 12$ outfits.

This extends to any number of sequential choices.

Factorial

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

$0! = 1$ (by convention; ensures formulas work)

$5! = 120$, $6! = 720$, $10! = 3,628,800$

Permutations (Order Matters)

The number of ways to arrange $r$ items from $n$ distinct items:

$$P(n, r) = \frac{n!}{(n-r)!}$$

When all $n$ items are arranged: $P(n, n) = n!$

Intuition: $n$ choices for first, $(n-1)$ for second, ..., $(n-r+1)$ for $r$th.

Example 1 — Permutations

How many ways can 3 students be chosen as president, VP, and secretary from a class of 20?

$P(20, 3) = \dfrac{20!}{17!} = 20 \times 19 \times 18 = 6840$

Combinations (Order Doesn't Matter)

The number of ways to choose $r$ items from $n$ without regard to order:

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

$C(n,r) = \dfrac{P(n,r)}{r!}$ — divide by $r!$ because arrangements of the same group are counted as one.

Example 2 — Combinations

How many ways can 3 students be chosen from 20 for a committee (no designated roles)?

$C(20, 3) = \dfrac{20!}{3! \times 17!} = \dfrac{6840}{6} = 1140$

Example 3 — Distinguishing P vs. C

Problem	P or C?	Reason
Arrange 5 books on a shelf