Labeled Ballot Paths and the Springer Numbers
William Y. C. Chen, Neil J.Y. Fan, Jeffrey Y.T. Jia
Abstract: The Springer numbers are defined in connection with the irreducible root
system of type B_{n} 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 B_{n}. We introduce the inversion code of a snake of type B_{n} and establish a
bijection between labeled ballot paths of length n and snakes of type B_{n}. 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 B_{n} 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]. Keywords: Springer number, snake of type B_{n}, labeled ballot path, labeled Dyck path, bijection Download: Pdf |