When Order Does Not Matter

Last timePutting Things in Order

Count the arrangements, then divide out the orderings you did not want. That one move turns the factorial into the choose count, which is the number sitting under most of probability.

Three people from ten will form a committee. How many committees are possible?

This is almost the medal problem from the previous lesson, where three of ten

runners took three different medals and the answer was seven hundred and

twenty. The difference is that a committee has no first place. The group of

Ana, Ben and Cara is the same committee however it was assembled, and the medal

count treated those six orderings as six different outcomes.

So the honest count is seven hundred and twenty divided by six, which is one

hundred and twenty. The whole lesson is why that division is allowed and how

to use it.

FIG 1Choosing two from five, counted twice over

step	step	what is counted	how many
1	ordered	pick a first then a second from five people	5 times 4, which is 20
2	the overcount	each pair appeared twice, once in each order: Ana then Ben, and Ben then Ana	2
3	is it uniform?	every pair was counted exactly twice, no pair more and no pair fewer	yes, which is what makes the next line legal
4	divide	twenty ordered picks, two orderings each	10 pairs
5	check by listing	AB AC AD AE BC BD BE CD CE DE	10 pairs, which agrees
6	the general shape	ordered count divided by the orderings of each selection	the choose count

6 steps

The third row is the one that matters and it is the row most treatments skip. Dividing a count by a number is only valid when every outcome was overcounted by that same number: if some pairs had been counted twice and others three times, no single division could repair it. Here the overcount is the same for every pair, because every pair of distinct people has exactly two orderings, so the division is exact. The habit worth forming is to say that sentence out loud before dividing, because when the uniformity fails the error is invisible in the arithmetic.

FIG 2The choose count

: how many items there are to choose from
: how many are being chosen. Order among them does not matter, which is the entire difference from the previous lesson
: read n choose k. It is a single number, not a fraction, despite being written as a stack in brackets
: the number of orderings of one selection, which is exactly what is being divided out
: how many are left behind. Its appearance in the second form is the symmetry of this lesson written down

Two forms of one number. The middle form is the one to compute with: k factors descending from n on the top, k factorial on the bottom, cancelling before multiplying. Ten choose three is ten times nine times eight over six, and cancelling the six against the nine and the eight before multiplying keeps every intermediate number small. The right hand form is the one that appears in print, and computing it literally is a bad idea, since the factorial of fifty two has sixty eight digits while the number of five card hands has only seven.

Choosing what goes in, or what stays out

Every selection of $k$ items leaves behind a selection of $n - k$ items, and

that pairing is exact: each selection has exactly one leftover, and each

leftover comes from exactly one selection. So the two counts are the same

number.

The practical use is immediate. Ninety eight items chosen from a hundred sounds

awful and is the same as two chosen from a hundred, which is four thousand nine

hundred and fifty, done in your head. Whenever one of the two numbers is small,

count that one.

FIG 3Pascal triangle, which is these counts in a table

	k = 0	k = 1	k = 2	k = 3	k = 4	k = 5
n = 1	1	1	0	0	0	0
n = 2	1	2	1	0	0	0
n = 3	1	3	3	1	0	0
n = 4	1	4	6	4	1	0
n = 5	1	5	10	10	5	1

Each row reads the same forwards and backwards, which is the symmetry: five choose two and five choose three are both ten, and those are the marked cells. Each entry is also the sum of the two above it, which has a direct reading rather than being a curiosity: to choose three from five, either the fifth item is in, and then two more come from the remaining four, or it is out, and all three come from the remaining four. Those two cases cannot overlap and cover everything, so the counts add. A nought here means the selection is impossible, since you cannot choose four items from three.

Where this number is hiding

The reason this count matters far beyond committees is that it appears inside

nearly every probability about repeated trials.

Flip a fair coin ten times and ask for the chance of exactly three heads. Every

particular sequence of ten flips is equally likely, and there are two to the

ten of them. The sequences with exactly three heads are the ones where you

choose which three of the ten positions are heads, and the number of such

choices is ten choose three, which is one hundred and twenty. So the chance is

one hundred and twenty out of one thousand and twenty four, which is about

twelve per cent.

That is the shape to recognise. Whenever a question asks how many of something

happened rather than which ones, a choose count converts one sequence into all

the sequences like it. The next lesson but one turns this into probability

properly, and the same number will reappear under the name binomial

coefficient when it multiplies the chance of a single sequence.

The lesson stops here

1 more paragraph to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

When Order Does Not Matter

Choosing what goes in, or what stays out

Where this number is hiding

1 more paragraph to go

This is the reading half

Read alongside