Week 76 of 125
TAOCP 5.1.4 Tableaux and Involutions
Sign up or sign in to tick these off and give this week a due date.
-
Young tableaux, a correspondence between permutations and pairs of tableaux (Robinson-Schensted), the hook length formula for counting tableaux, and involutions (permutations that are their own inverse).
Time About 9 hours this week
Why it matters
The correspondence gives a slick way to find the longest increasing subsequence, a common interview and diff-algorithm topic. It is also one of the most beautiful bijections in combinatorics.
Before you start
- 5.1.1 Inversions
How to approach it
Implement the insertion procedure that builds the tableau from a permutation, and check that the length of the first row equals the longest increasing subsequence length. Verify the hook length formula on small shapes.
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
- Bumping into the wrong row during insertion. Trace carefully with pencil.