Abstract:  Let [n] = {1, 2, ..., n}. It is well known that the number of labeled trees on [n] equals n^n-2, and the number of rooted trees on [n] equals n^n-1 [1, 4]. Recently, Postnikov [2] derived the following identity on binary trees and asked for a combinatorial proof [2]. We adopt the terminology of Postnikov [2]. Given a binary tree T and a vertex v of T, we use h(v) to denote the "hook-length" of v, namely, the number of descendants of v (including v itself). Postnikov [2] obtained the following identity.

  AMS Classification:  05A15, 05A19.

  Keywords:  Binary tree, labeled tree, hook length.

  Download:   PDF