2
$\begingroup$

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?

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Perfect! Thanks! $\endgroup$ Commented Oct 17, 2019 at 9:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .