Knuth's hook length formula for trees

Tags: #theorem

Statement

Let T be a plane binary tree, and let fT be the number of increasing labelings of vertices of T.

We define the hook length of a vertex vT as the number of descendants of v including v. (ie. the size of the subtree rooted at v).

Then,

fT=n!vTh(v)

20260220_135701.jpg

Proof