A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests

Abstract

For a fixed sequence of $n$ positive integers $(a,\bar{b}) := (a, b, b,\ldots, b)$, an $(a,\bar{b})$-parking function of length $n$ is a sequence $(p_1, p_2, \ldots, p_n)$ of positive integers whose nondecreasing rearrangement $q_1 \leq q_2 \leq \cdots \leq q_n$ satisfies $q_i \leq a+(i-1)b$ for any $i=1,\ldots, n$. A $(a,\bar{b})$-forest on $n$-set is a rooted vertex-colored forests on $n$-set whose roots are colored with the colors $0, 1, \ldots, a-1$ and the other vertices are colored with the colors $0, 1, \ldots, b-1$. In this paper, we construct a bijection between $(bc,\bar{b})$-parking functions of length $n$ and $(bc,\bar{b})$-forests on $n$-set with some interesting properties. As applications, we obtain a generalization of Gessel and Seo's result about $(c,\bar{1})$-parking functions [Ira M. Gessel and Seunghyun Seo, Electron. J. Combin. $\textbf{11}$(2)R27, 2004] and a refinement of Yan's identity [Catherine H. Yan, Adv. Appl. Math. $\textbf{27}$(2―3):641―670, 2001] between an inversion enumerator for $(bc,\bar{b})$-forests and a complement enumerator for $(bc,\bar{b})$-parking functions.

Keywords

• bijection
• forests
• parking functions
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]