TAOCP 1.2.6 Binomial Coefficients (part 2): reading guide

Part 2 finishes the section: summing products of binomial coefficients (Vandermonde-style convolution), negating the upper index, and the general strategy for attacking a sum involving binomials. It closes with related numbers like multinomial coefficients and Stirling numbers.

Time About 8 hours this week

Why it matters

This is where you learn to actually evaluate sums that pop out of algorithm analysis, rather than just recognize them.

Before you start

1.2.6 Binomial Coefficients (part 1)

How to approach it

Go back over your part 1 summary first. For each worked example of a tricky sum, try to do it yourself before reading Knuth's solution. Expect to reread a few pages; that is normal.

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. Many people find this the hardest exercise set in chapter 1. If you get through a handful of M20s you are doing well.

Traps

Losing track of signs when negating the upper index.
Spending three weeks here. Set a timer, move on, and revisit later; Vol 3 will send you back anyway.