Factorials and Combinations

Some probability questions need a count first: how many different ways can 3 of 10 quiz answers be right? Listing them all would take a long time. Two tools do the counting for you: the factorial and the combination.

Factorials: counting orders

How many ways can you line up 5 different books on a shelf? There are 5 choices for the first spot. Once that book is placed, 4 remain for the second spot, then 3, then 2, then 1. Multiply:

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

That product is written $5!$, read "5 factorial". In general,

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

and by definition $0! = 1$. Factorials grow fast: $10! = 3{,}628{,}800$.

Combinations: counting choices

Often the order does not matter. A team of Ana and Ben is the same team as Ben and Ana. Counting ordered choices of 2 from 4 people gives $4 \times 3 = 12$, but that counts each team twice, once in each order. Divide by the $2! = 2$ orders: 6 teams.

The general rule is the combination, the number of ways to choose k items from n when order does not matter:

$${}_nC_k = \binom{n}{k} = \frac{n!}{k!\,(n - k)!}.$$

Read it "n choose k". Both notations mean the same thing; on a calculator it is usually nCr, and in Bluebook you can type 10C3.

Useful facts

• ${}_nC_0 = 1$ and ${}_nC_n = 1$: one way to choose nothing, one way to choose everything.
• ${}_nC_k = {}_nC_{n-k}$: choosing the 3 questions that are right is the same as choosing the 7 that are wrong, so ${}_{10}C_3 = {}_{10}C_7 = 120$.
• ${}_nC_1 = n$: there are n ways to choose one item.

Order or no order?

In Unit 2 the combination appears inside a probability formula, counting the different orders in which successes and failures can happen. Being quick and sure with ${}_nC_k$ now makes that formula much easier.