TAOCP Vol 1: Fundamental Algorithms · Week 22
TAOCP 1.2.6 Binomial Coefficients (part 1): reading guide
Part 1 covers what binomial coefficients count, their definition for general upper index, and the core toolbox of identities: symmetry, absorption, the addition formula (Pascal's rule) and the binomial theorem. Aim to get through the main list of basic properties.
Time About 7 hours this week
Why it matters
Binomial coefficients are the vocabulary of combinatorics and of probability analysis for algorithms. Half the derivations in Vol 3 lean on these identities.
Before you start
- 1.2.5 Permutations and Factorials
- 1.2.3 Sums and Products
How to approach it
This is one of the densest sections in Vol 1, so it is split over two weeks. This week: build Pascal's triangle up to row 10 by hand and verify each basic identity against it. Make your own one-page summary of the identities with a numeric example next to each. Stop around the point where the text turns to harder summation techniques.
Exercises
Do the low-rated exercises tied to the identities you read this week. Leave anything involving the later sum techniques for part 2.
Traps
- Assuming the upper index must be a nonnegative integer. Knuth allows general values, and that generality matters.
- Trying to memorize identities instead of understanding them through Pascal's triangle.