For a labeled tree $T$ on $\{1,2,...,n\}$ an inversion of $T$ is a pair $1 < i < j \leq n$ such that $j$ belongs to the unique path from $1$ to $i$ (we think of $T$ as being rooted at $1$). Let $\mathrm{inv}(T)$ denote the number of inversions of $T$.

Define the generating function $f(q) := \sum_{T} q^{\mathrm{inv}(T)}$ where the sum is over all labeled trees on $\{1,2,...,n\}$.

Then it is known that $f(-1)$ is the number of alternating permutations in $\mathfrak{S}_n$ (i.e., the so-called "Euler number"). See e.g. Goulden-Jackson 3.3.49(d).

Question: Is there a simple proof of this result via a sign-reversing involution?


J.-J. Pansiot, Nombres d'Euler et Inversions dans les Arbres, Europ. J. Combin. 3 (1982), 259–262, uses a sign-reversing involution to show that $f(-1)$ is the number of increasing trees on $[n]$ in which every vertex other than the root has an even number of children. In Pansiot's paper he gives a reference to a paper of Viennot (that I have not looked at) that shows that these trees are counted by the Euler numbers.

  • $\begingroup$ Perfect! Thanks! $\endgroup$ Oct 17 '19 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.