On Han's Hook Length Formulas for Trees

  • William Y.C. Chen
  • Oliver X.Q. Gao
  • Peter L. Guo

Abstract

Recently, Han obtained two hook length formulas for binary trees and asked for combinatorial proofs. One of Han's formulas has been generalized to $k$-ary trees by Yang. Sagan has found a probabilistic proof of Yang's extension. We give combinatorial proofs of Yang's formula for $k$-ary trees and the other formula of Han for binary trees. Our bijections are based on the structure of $k$-ary trees associated with staircase labelings.

Published
2011-07-29
Article Number
P155