Permutations and combinations: count the orders, then divide them out

Permutations & combinations

Why is the number of ways to choose k things from n equal to n(n−1)…(n−k+1) divided by k!, and why does Pascal’s triangle give the same numbers by adding?

Fill k slots one by one and multiply the choices left at each step: that counts ordered picks. Every unordered group was counted once for each of its k! orders, so divide. Pascal’s triangle reaches the same number by a different route: the last item is either in the group or not.

High school
Multiplication principle
Permutations
Combinations
Pascal's triangle

n

k

\binom{n}{k} = \dfrac{A_n^k}{k!}

$A_n^k = n(n-1)\cdots(n-k+1)$: 60
$k!$: 6
$\binom{n}{k}$: 10
$\binom{n-1}{k-1} + \binom{n-1}{k}$: 10
$\binom{n}{n-k}$: 10

k ≤ nyes: there are groups to count

Guided tour

1Fill the slots
Pick $3$ of $5$ people in order: $5$ choices for the first slot, $4$ left for the second, $3$ for the third. Each choice can follow every earlier one, so the counts multiply: $5\times4\times3=60$ ordered picks.
2Divide out the orders
A group like $\{A,B,C\}$ appeared in the $60$ as $ABC$ , $ACB$ , $BAC$ , $BCA$ , $CAB$ and $CBA$ : once for each of its $3!=6$ orders. Every group is counted exactly $6$ times, so there are $60\div6=10$ groups.
3The triangle adds instead
Look at the last person. Groups that include them need $2$ more from the other $4$ : $\binom42=6$ (blue). Groups that leave them out take all $3$ from the other $4$ : $\binom43=4$ (green). $6+4=10$ , the highlighted cell. The triangle is built from this rule alone, with no multiplication.
4Choosing in = choosing out
Choosing $2$ of $7$ to go is the same as choosing the $5$ who stay: $\binom72=\binom75=21$ . That is why every row of the triangle reads the same backwards.
5Edge cases
Choosing $0$ things can be done in exactly one way, doing nothing, so $\binom n0=1$ and $0!=1$ . Ask for more than you have and a slot runs out of choices: a factor $0$ appears and the count is $0$ .

Explanation

1
The multiplication principle
If a task is done in steps, with $m_1$ ways for the first step and, whatever happened, $m_2$ ways for the second, then there are $m_1m_2$ ways in all: each of the $m_1$ starts branches into $m_2$ . Everything in this chapter is this one rule applied carefully.
2
Permutations: order counts
Fill $k$ slots from $n$ distinct things. The first slot has $n$ choices, the next $n-1$ and so on, one fewer each time:
$A_n^k=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}$
With $k=n$ this is $n!$ , the number of ways to line up all $n$ .
3
Combinations: divide out the order
Count the ordered picks in two steps: first choose the group, then put it in order. The second step has $k!$ ways whatever the group is, so by the multiplication principle
$A_n^k=\binom nk\cdot k!\qquad\Longrightarrow\qquad\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k!}$
This is why the division is exact: it undoes a multiplication.
4
Pascal's rule and the row sums
Single out one element. Every group of $k$ either contains it or does not, never both:
$\binom nk=\binom{n-1}{k-1}+\binom{n-1}{k}$
The board builds the triangle from this rule and $\binom00=1$ alone, and the highlighted cell always matches the multiplicative formula.
Adding a whole row counts all subsets of $n$ things. Each element is in or out, two choices $n$ times, so the row sums to $2^n$ .

Check yourself

Q01

How many ways can a president and a secretary be chosen from $8$ people?

Q02

Why do we divide by $k!$ to get $\binom nk$ ?

Q03

What is $\binom{10}{8}$ ?

Keep exploring

Turn this lab into a videoUse this lab as the script for a narrated explainer you can share. The prompt below goes to the video creator, where you can edit it first.

Make the video

View · display