Putting Things in Order

Last timeOne Choice After Another

Apply the multiplication rule until the pile runs out and the factorial appears. It is the fastest growing count in ordinary use, and it is why some problems can never be solved by trying everything.

Five books go on a shelf. How many different shelves are possible?

This is the multiplication rule from the previous lesson with one new feature:

the options run out as you go.

FIG 1Filling the shelf, one position at a time

step	position	books still available	options here	running total
1	first	all five	5	5
2	second	the four not yet shelved	4	20
3	third	three left	3	60
4	fourth	two left	2	120
5	fifth	whatever remains	1	120
6	the answer	nothing left to place		120 shelves

6 steps

The condition from the previous lesson holds at every row, and it is worth checking rather than assuming. After the first book is placed, which four remain depends on what was chosen, but there are always exactly four, and the rule needs only the count to be fixed. The last row contributes a factor of one and is often skipped in the arithmetic, which is harmless, but writing it down keeps the pattern visible: the product runs all the way to one. That product has a name and a symbol, and both are shorthand for exactly this calculation.

FIG 2The factorial, which is the product above

: how many items are being arranged. All of them are placed and all of them are distinguishable
: read n factorial. The exclamation mark is notation for the product on the right and nothing more, which is worth insisting on because it is usually presented as a definition
: defined to be one. There is exactly one way to arrange nothing, namely the empty arrangement, and this is not a convention adopted for convenience but the count coming out right
: every whole number between the two ends, each appearing exactly once

Five books give one hundred and twenty shelves, which is already more than anybody would list. The thing to carry forward is not the symbol but its origin: a factorial is what the multiplication rule produces when the pile empties as you go. That origin is what lets you rebuild the formula when a problem is slightly different, which the rest of this lesson is about, instead of hunting for the variant formula that fits.

How fast this grows

The factorial is the fastest growing count anybody meets in ordinary work, and

it is faster than exponential growth, which the previous course already

established as alarming.

The reason is visible in the construction. An exponential multiplies by the

same factor at every step. A factorial multiplies by a factor that itself

increases: going from ten items to eleven multiplies the count by eleven, and

going from twenty to twenty one multiplies it by twenty one. There is no fixed

base, so no exponential can keep up for long.

FIG 3Three ways of growing, compared at the same sizes

	n squared	two to the n	n factorial	how long to list them at
n = 5	25.000000	32.000000	120.000000	0.000000
n = 10	100.000000	1024.000000	3628800.000000	3.600000
n = 13	169.000000	8192.000000	6227020800.000000	6227.000000
n = 15	225.000000	32768.000000	1307674368000.000000	1307674.000000
n = 20	400.000000	1048576.000000	2430000000000000000.000000	2430000000000.000000
n = 25	625.000000	33554432.000000	1.55e+25	15500000000000000000.000000

The last column is in seconds. The two marked cells are the boundary of what is possible: ten items can be enumerated in under four seconds, and twenty items would take seventy seven thousand years. Between those two rows nothing about the problem changed except its size by a factor of two. Notice also how badly the three columns separate. At n equals five the three counts are within a factor of five of each other, which is why small examples give no warning at all, and at n equals twenty five the factorial is seventeen orders of magnitude above the exponential. Reading this table as a chart would need the squashed axis of the previous course, since no linear scale can hold both ends.

The practical reading is a boundary rather than a formula. Around ten or eleven

items, trying every arrangement is free. Around thirteen it is a real

computation. Beyond about fifteen it is not a slow approach, it is not an

approach at all, and no faster machine changes that: a thousandfold speedup

buys about three more items. A problem whose only known method is checking all

arrangements of twenty things needs a different method, and recognising that

early is worth more than any amount of optimisation.

The lesson stops here

2 more paragraphs 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

Putting Things in Order

How fast this grows

2 more paragraphs to go

This is the reading half

Read alongside