Bijections for Entringer families (Q607373)

A down-up permutation \(\pi=\pi_1\pi_2\cdots\pi_n\) of \([n]=\{1,2,\ldots,n\}\) is a permutation of \([n]\) such that \(\pi_1>\pi_2<\pi_3>\pi_4<\cdots\). \textit{D. André} [``Développements de \(\sec x\) et \(\tan x\)'', C. R. LXXXVIII, 965--979 (1879; JFM 11.0187.01)] showed that the number of down-up permutations of \([n]\) is given by \(E_n\), the \(n\)-th Euler number (\(\sum_{n\geq0}E_n\frac{x^n}{n!}=\tan x+\sec x\)). \textit{R.C. Entringer} [``A combinatorial interpretation of the Euler and Bernoulli numbers'', Nieuw Arch. Wiskd., III. Ser. 14, 241--246 (1966; Zbl 0145.01402)] gave a refinement of this result by proving that the number of down-up permutations of \([n]\) according to the first element is given by the Seidel triangle (\(E_{n,k}\), [\textit{L. Seidel}, ``Über eine einfache Entstehungsweise der Bernoullischen Zahlen and einiger verwandten Reihen,'' Sitzungsber. Münch. Akad. 4, 157--187 (1877)]). Several authors presented combinatorial interpretations for \(E_{n,k}\) in both down-up permutations and increasing trees, see \textit{C. Poupard} [``De nouvelles significations énumératives des nombres d'Entringer'', Discrete Math. 38, 265--271 (1982; Zbl 0482.05006), ``Two other interpretations of the Entringer numbers'', Eur. J. Comb. 18, No. 8, 939--943 (1997; Zbl 0886.05011)] and \textit{A. G. Kuznetsov}, \textit{I. M. Pak} and \textit{A. E. Postnikov} [``Increasing trees and alternating permutations'', Russ. Math. Surv. 49, No. 6, 79--114 (1994); translation from Usp. Mat. Nauk 49, No. 6, 79--110 (1994; Zbl 0842.05025)]. The main goal of this paper is to provide bijections between the different models for \(E_{n,k}\) as well as some new interpretations. In particular, the authors present an explicit bijection between down-up permutations and increasing trees.