Back to the on-screen lesson ·
Ordered and unordered selections, why the difference is a factor of k factorial, and which a question wants.
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.
You will decide, for any selection problem, whether the order of the chosen things forms part of the answer and whether a thing may be chosen twice, and then count the selections with the model those two answers pick out. You will also turn a count into a probability by dividing by the size of an equally likely sample space.
The product rule counts a choice made in stages, and that is still the whole engine here. What this lesson adds is one extra question asked of every selection — whether two selections that differ only in order are the same answer — and a division when they are.
A permutation of $k$ things from $n$ is an ordered selection with no repeats, counted by $P(n, k) = n(n-1)\cdots(n-k+1) = \dfrac{n!}{(n-k)!}$. A combination is the same selection with the order discarded, counted by $\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$. The symbol $\binom{n}{k}$ is read $n$ choose $k$, and $k!$ is the number of orders of $k$ things.
Every selection problem is settled by two questions. Does the order of the chosen things form part of the answer? and may a thing be chosen more than once? The four answers give the four counts:
The second of those is the only one that needs an argument, and the argument is one line: count the ordered selections, then notice that each unordered selection was counted exactly $k!$ times, once for each order of the things chosen. So divide by $k!$. That division is the word unordered.
Two identities are worth having by heart because they save real work: $\binom{n}{k} = \binom{n}{n-k}$ — choosing who is in is choosing who is out — and $\sum_{k} \binom{n}{k} = 2^{n}$, because a subset is a yes-or-no decision per element.
Another way: table
The same four questions, asked of eight people.
| Question | Model | Count |
|---|---|---|
| Gold, silver, bronze | ordered, no repeats | $8 \times 7 \times 6 = 336$ |
| A committee of three | unordered, no repeats | $336 / 6 = 56$ |
| A three-digit code from eight symbols | ordered, repeats | $8^{3} = 512$ |
| A seating order for all eight | all arranged | $8! = 40320$ |
Another way: steps
Using $P(n,k)$ where $\binom{n}{k}$ is wanted. The commonest error in the whole unit, and it always overcounts by exactly $k!$. The test is step 2 above: write two selections that differ only in order and ask whether they are the same answer.
Dividing by $k$ instead of $k!$. Three chosen people have six orders, not three.
Allowing repeats without noticing. Choose three of the eight forbids them; a three-symbol code from eight symbols allows them, and the two counts differ by more than a factor of nine.
Counting selections when the question asks for a probability. A count is not a probability. It becomes one only when it is divided by the count of the whole sample space — and only when those outcomes are equally likely.
Choose three from $\{a, b, c, d, e\}$ in order: $5 \times 4 \times 3 = 60$ ways.
Product rule, one stage per place.
The set $\{a, b, c\}$ appears as $abc$, $acb$, $bac$, $bca$, $cab$, $cba$ — six of the sixty.
Every set appears $3! = 6$ times.
So there are $60 / 6 = 10$ subsets of size three.
And $\binom{5}{3} = 10$.
A hand is held all at once, so the order the cards arrived in is not part of it: $\binom{52}{5} = 2598960$.
Unordered, no repeats.
Hands that are all hearts: $\binom{13}{5} = 1287$.
The same model on a smaller set.
So a flush in hearts has probability $1287 / 2598960 \approx 0.000495$.
Both counts unordered, so they are comparable.
Two teams naming the same four people in a different order are the same team, so the count is unordered.
Answer the order question first.
Ordered: $9 \times 8 \times 7 \times 6 = 3024$, and each team is reached $4! = 24$ ways.
So $3024 / 24 = 126$ teams, which is $\binom{9}{4}$.
A club has $9$ members. How many different subsets of each size can be chosen from it?
| How many | |
|---|---|
| Subsets of size $1$ | |
| Subsets of size $2$ | |
| Subsets of size $3$ |
$9$ runners finish a race with no ties. In how many ways can the gold, silver and bronze medals be awarded?
Answer:
How many three-person committees, with no titles and no distinct roles, can be formed from $9$ people?
Four things are chosen from $8$, none of them twice. Give the ordered count and the unordered one.
Ordered: p. Unordered: q.
A committee of three is chosen from $10$ people, every committee equally likely. What is the probability that one named person is on it?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Take $n = 6$. Put these four counts in order, smallest first.
Number the steps in order (write the number in the box):
You can tell an ordered selection from an unordered one, count either, and divide one count by another to get a probability. Say in your own words why the unordered count is the ordered count divided by k factorial rather than by k.
8. Your turn: how many four-person teams can be chosen from nine people, step 3