Back to the on-screen lesson ·
Counting with order, and the division by k factorial that turns it into counting without — together with the case where that division is wrong.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to decide whether a count is ordered or unordered by asking whether swapping two chosen objects changes the outcome, work out an ordered count as a product of decreasing factors, and divide by k factorial when order does not matter. You will also be able to check the hypothesis that division rests on — that every outcome was counted the same number of times — and to split into cases when it fails, as it does whenever repeats are allowed.
Lesson 16 ended on the move this lesson is built from: count the easy, ordered thing, then divide by the number of times each answer appeared. Everything here is that move carried out carefully, and the only new content is what the division factor is.
$n!$ is $n \times (n-1) \times \cdots \times 1$, with $0! = 1$. A permutation of $k$ objects from $n$ is an ordered selection, counted by $P(n, k) = n(n-1)\cdots(n-k+1)$. A combination is an unordered selection, counted by $\binom{n}{k} = P(n,k)/k!$ and read $n$ choose $k$.
Ordered. To fill $k$ positions from $n$ objects with no repeats: $n$ choices for the first, $n-1$ for the second, down to $n-k+1$ for the last. $$P(n, k) = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}$$ The factorial form is a convenience for algebra and the product form is what to think with, because the product form is the count.
Unordered. A committee of $k$ has no first member, so each committee has been counted once for every way its members could have been ordered, which is $k!$ times. Dividing, $$\binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{k!\,(n-k)!}.$$ That division is the only idea in the lesson, and it is worth stating as a principle: when every outcome has been counted the same number of times, divide by that number. The clause the same number of times is a hypothesis, and a count where different outcomes are overcounted by different amounts cannot be fixed this way at all.
Which one a question wants is settled by a single test: would swapping two of the chosen objects give a different outcome? President and treasurer, yes — ordered. A committee of two, no — unordered. Three medals of different metals, yes. Three identical prizes, no.
$\binom{n}{k} = \binom{n}{n-k}$, because choosing who is in is the same as choosing who is out. That is a bijection, not an algebraic manipulation, and it is the kind of proof the next lesson is full of.
Another way: steps
Another way: example
Five people, choose three for a committee. Ordered: $5 \times 4 \times 3 = 60$. Each committee of three has $3! = 6$ orderings, so there are $60/6 = 10$ committees. And $\binom{5}{3} = \binom{5}{2} = 10$: choosing the three who are in is choosing the two who are out.
Choosing two things from $n$, the answer depends entirely on two questions — does order matter, and may an object be reused?
| Order matters | Repeats allowed | Count | Example |
|---|---|---|---|
| yes | yes | $n^2$ | a two-letter code |
| yes | no | $n(n-1)$ | president and treasurer |
| no | no | $n(n-1)/2$ | a committee of two |
| no | yes | $n(n+1)/2$ | a two-scoop cone, flavours repeatable |
The last row is the awkward one and is worth deriving rather than remembering: the unordered-with-repeats count is the $n$ pairs of identical objects plus the $n(n-1)/2$ pairs of distinct ones. It cannot be got by dividing $n^2$ by two, because the pairs with a repeat were counted once each and the rest twice each — exactly the case where the division principle does not apply.
Dividing when order matters. Three different medals are an ordered count; dividing by $3!$ answers a question nobody asked.
Not dividing when it does not. Counting committees as ordered selections overcounts by $k!$.
Dividing an unevenly overcounted total. The two-scoop cone above. Check that every outcome really was counted the same number of times.
Reaching for the factorial formula first. $\binom{52}{5}$ as $52!/(5!\,47!)$ is correct and unusable; as $(52 \times 51 \times 50 \times 49 \times 48)/120$ it is arithmetic you can do.
It is easy to read $\binom{n}{k} = P(n,k)/k!$ as make an ordered list and then forget the order, and the division only works because every unordered outcome arises from exactly $k!$ ordered ones. Change the situation slightly — allow repeats, or make some of the chosen objects identical — and the number of ordered lists per outcome stops being constant, and the division silently gives a wrong answer with no remainder to warn you. The hypothesis is the point, not the formula.
From $8$ runners, how many ways to award gold, silver and bronze? The medals differ, so order matters: $8 \times 7 \times 6 = 336$.
Ordered: no division.
From the same $8$, how many ways to choose three to go to the final? The three places are the same, so order does not: $336 / 3! = 56$.
Unordered: divide by the arrangements of the chosen.
Six times as many medal ceremonies as squads, and the six is $3!$ — the number of ways one squad could have been arranged on the podium.
The ratio is the division factor, made concrete.
Two scoops from $4$ flavours, repeats allowed, order not mattering. The ordered count is $4^2 = 16$.
Start with the easy ordered count.
But $16/2 = 8$ is wrong. The four same-flavour pairs were counted once each, and the other twelve ordered pairs were counted twice each.
Check that the overcounting is even. It is not.
Split instead: $4$ same-flavour cones plus $\binom{4}{2} = 6$ mixed ones, so $10$. When outcomes are overcounted unevenly, split into cases rather than dividing.
Cases, from lesson 9, rescue the count.
A hand is a set of cards — the order they were dealt in does not change the hand — so this is unordered.
Decide ordered or unordered first, always.
Ordered: $52 \times 51 \times 50 \times 49 \times 48$. Each hand arises from $5! = 120$ of those deals, and from exactly $120$, because the five cards are distinct.
Check the overcounting is even before dividing.
So the answer is that product divided by $120$, which is $2{,}598{,}960$. Working from the product form kept the arithmetic to five multiplications and one division; the factorial form would have needed $52!$, which no calculator will give you.
A club has $11$ members. Fill in both counts for choosing two of them.
| How many ways | |
|---|---|
| A president and then a treasurer | |
| A committee of two |
In how many ways can a committee of two be chosen from $12$ people?
Answer:
In how many ways can gold, silver and bronze be awarded among $10$ runners?
Answer:
Match each question to the kind of count it needs.
| Ordered — swapping two chosen objects gives a different outcome | Unordered — the ordered count must be divided by the arrangements | |
|---|---|---|
| How many ways to seat five people in a row | ||
| How many ways to choose three books from ten to take on holiday | ||
| How many three-letter codes from a 26-letter alphabet, letters repeatable | ||
| How many ways to pick a president and then a treasurer from a club | ||
| How many two-element subsets a set of nine has |
A club has $6$ members. Put these four counts in order, smallest first.
Number the steps in order (write the number in the box):
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A club has $11$ members. Fill in both counts for choosing two of them.
| How many ways | |
|---|---|
| A president and then a treasurer | |
| A committee of two |
You can tell an ordered count from an unordered one and divide correctly between them. Say in your own words why a committee of k is counted k factorial times by an ordered selection, and give a case where dividing the ordered count would be wrong. Next: the numbers that unordered counts produce, and the triangle they arrange themselves into.
10. Your turn: how many five-card hands from a standard $52$-card deck?, step 3