Natural Bijections Among Combinatorial Objects Counted by Springer Numbers
An explicit chain of combinatorial bijections proving that four families of objects are all equinumerous with the Springer numbers (the type-B analog of the Euler numbers): snakes, labeled ballot paths, rc-invariant alternating permutations, and weakly increasing 3-dimensional permutations. Teaches how a 'natural' bijective correspondence replaces intricate or non-constructive enumeration proofs and makes several interpretations of the same sequence manifestly equivalent.
2501.00335
The Springer numbers are a type-B analog of the Euler numbers, defined by the exponential generating function 1/(cos x - sin x); they enumerate several distinct families of combinatorial objects. Thi…