TAOCP 1.2.5 Permutations and Factorials: reading guide

Counting arrangements, factorials, and how fast n! grows, including Stirling's approximation. Knuth also extends factorials to non-integers via the gamma function and shows how to count the power of a prime dividing n!.

Time About 5 hours this week

Why it matters

Factorials set the lower bound for comparison sorting (you need about lg n! comparisons) and they tell you instantly when brute force over permutations is hopeless.

Before you start

1.2.3 Sums and Products
1.2.4 Integer Functions

How to approach it

Read the counting arguments carefully and do them on small n. Compute a few values of Stirling's approximation against real n! to feel the error. The gamma function part is fine to read for the idea and skim the proofs.

Exercises

Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.

Traps

Getting lost in the gamma function. It is optional depth for now.
Off-by-one between permutations of n things and arrangements of k out of n.