A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2009-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2714/pdf |
| _version_ | 1797270341011111936 |
|---|---|
| author | Heesung Shin Jiang Zeng |
| author_facet | Heesung Shin Jiang Zeng |
| author_sort | Heesung Shin |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:02:43Z |
| format | Article |
| id | doaj.art-3bc6524326c44b839a37e7d341be54c2 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:02:43Z |
| publishDate | 2009-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-3bc6524326c44b839a37e7d341be54c22024-03-07T14:45:40ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502009-01-01DMTCS Proceedings vol. AK,...Proceedings10.46298/dmtcs.27142714A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forestsHeesung Shin0Jiang Zeng1Institut Camille JordanInstitut Camille JordanFor 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.https://dmtcs.episciences.org/2714/pdfbijectionforestsparking functions[math.math-co] mathematics [math]/combinatorics [math.co][info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Heesung Shin Jiang Zeng A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests Discrete Mathematics & Theoretical Computer Science bijection forests parking functions [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests |
| title_full | A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests |
| title_fullStr | A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests |
| title_full_unstemmed | A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests |
| title_short | A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests |
| title_sort | further correspondence between bc bar b parking functions and bc bar b forests |
| topic | bijection forests parking functions [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2714/pdf |
| work_keys_str_mv | AT heesungshin afurthercorrespondencebetweenbcbarbparkingfunctionsandbcbarbforests AT jiangzeng afurthercorrespondencebetweenbcbarbparkingfunctionsandbcbarbforests AT heesungshin furthercorrespondencebetweenbcbarbparkingfunctionsandbcbarbforests AT jiangzeng furthercorrespondencebetweenbcbarbparkingfunctionsandbcbarbforests |