A combinatorial proof of {P}ostnikov's identity and a generalized enumeration of labeled trees
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.
- A refinement of the formula for \(k\)-ary trees and the Gould-Vandermonde's convolution
- Two kinds of hook length formulas for complete \(m\)-ary trees
- Generalized (\(P\), \(\omega\))-partitions and generating functions for trees
- Labelled and unlabelled enumeration of k-gonal 2-trees
- Two bijective proofs for the arborescent form of the Good-Lagrange formula and some applications to colored rooted trees and cacti
- A combinatorial identity for rooted labeled forests
- A generalized enumeration of labeled trees and reverse Prüfer algorithm
- scientific article; zbMATH DE number 2186866 (Why is no real title available?)
- Postnikov identities and Seo's formulas
- Bijections on rooted trees with fixed size of maximal decreasing subtrees
- More Trees and Power Sums
- Some refined enumerations of hybrid binary trees
- Labeled trees, functions, and an algebraic identity
- Bilabelled increasing trees and hook-length formulae
- Hook length polynomials for plane forests of a certain type
- Some enumerative properties of parking functions
- Two short proofs of Kemp's identity for rooted plane trees
- A refinement of Cayley's formula for trees
- \((k,m)\)-Catalan numbers and hook length polynomials for plane trees
- An insertion algorithm and leaders of rooted trees
- On Postnikov's hook length formula for binary trees
- Trees, functional equations, and combinatorial Hopf algebras
This page was built for publication: A combinatorial proof of {P}ostnikov's identity and a generalized enumeration of labeled trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1773142)
