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 v∈T as the number of descendants of v including v. (ie. the size of the subtree rooted at v).

Then,

fT=n!∏v∈Th(v)

20260220_135701.jpg

Proof