A combinatorial proof of {P}ostnikov's identity and a generalized enumeration of labeled trees (Q1773142): Difference between revisions

The following formula was shown to hold in a talk by Postnikov at Stanley's 60th Birthday Conference: \[ (n+1)^{n-1} = \sum_{\mathbf b} \frac{n!}{2^n} \prod_{v \in V({\mathbf b})} \left( 1+ \frac{1}{h(v)} \right), \] where the sum is taken over unlabeled binary trees \(\mathbf b\) on \(n\) vertices and \(h(v)\) denotes the number of descendants of \(v\) (including \(v\)). Postnikov derived the identity from the study of a combinatorial interpretation of mixed Euler numbers, and asked for a combinatorial proof of the identity. In this paper such a proof is given by finding a bijection between the set of labeled bicolored forests on \(\{1,2,\dots,n\}\) and a certain set of labeled bicolored binary trees. In addition, some formulae are given for the number of labeled \(k\)-ary trees, rooted labeled trees, and labeled plane trees.