Labeled Ballot Paths and the Springer Numbers

William Y. C. Chen, Neil J.Y. Fan and Jeffrey Y.T. Jia

  Abstract:  The Springer numbers are defined in connection with the irreducible root system of type Bn and also arise as the generalized Euler and class numbers introduced by Shanks. Combinatorial interpretations of the Springer numbers have been found by Purtill in terms of André signed permutations, and by Arnol'd in terms of snakes of type Bn. We introduce the inversion code of a snake of type Bn and establish a bijection between labeled ballot paths of length n and snakes of type Bn. Moreover, we obtain the bivariate generating function for the number B(n, k) of labeled ballot paths starting at (0, 0) and ending at (n, k). Using our bijection, we find a statistic α such that the number of snakes π of type Bn with α(π) = k equals B(n, k). We also show that our bijection specializes to a bijection between labeled Dyck paths of length 2n and alternating permutations on [2n].

  AMS Classification:   05A05, 05A19

  Keywords: Springer number, snake of type Bn, labeled ballot path, labeled Dyck path, bijection

  Download:  pdf