Abstract
For positive integers a and b, an (a, b̄)-parking function of length n is a sequence (p1, . . ., pn) of nonnegative integers whose weakly increasing order q1 ≤ . . . ≤ qn satisfies the condition qi < a + (i - 1)b. In this paper, we give a new proof of the enumeration formula for (a, b̄)-parking functions by using of the cycle lemma for words, which leads to some enumerative results for the (a, b̄)-parking functions with some restrictions such as symmetric property and periodic property. Based on a bijection between (a, b̄)-parking functions and rooted forests, we enumerate combinatorially the (a, b̄)-parking functions with identical initial terms and symmetric (a, b̄)-parking functions with respect to the middle term. Moreover, we derive the critical group of a multigraph that is closely related to (a, b̄)-parking functions.
| Original language | English |
|---|---|
| Pages (from-to) | 345-360 |
| Number of pages | 16 |
| Journal | Graphs and Combinatorics |
| Volume | 26 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 2010 Mar 8 |
Fingerprint
Keywords
- Critical group
- Cycle lemma
- Labeled rooted forest
- Parking function
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
Cite this
Cycle lemma, parking functions and related multigraphs. / Eu, Sen-Peng; Fu, Tung Shan; Lai, Chun Ju.
In: Graphs and Combinatorics, Vol. 26, No. 3, 08.03.2010, p. 345-360.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - Cycle lemma, parking functions and related multigraphs
AU - Eu, Sen-Peng
AU - Fu, Tung Shan
AU - Lai, Chun Ju
PY - 2010/3/8
Y1 - 2010/3/8
N2 - For positive integers a and b, an (a, b̄)-parking function of length n is a sequence (p1, . . ., pn) of nonnegative integers whose weakly increasing order q1 ≤ . . . ≤ qn satisfies the condition qi < a + (i - 1)b. In this paper, we give a new proof of the enumeration formula for (a, b̄)-parking functions by using of the cycle lemma for words, which leads to some enumerative results for the (a, b̄)-parking functions with some restrictions such as symmetric property and periodic property. Based on a bijection between (a, b̄)-parking functions and rooted forests, we enumerate combinatorially the (a, b̄)-parking functions with identical initial terms and symmetric (a, b̄)-parking functions with respect to the middle term. Moreover, we derive the critical group of a multigraph that is closely related to (a, b̄)-parking functions.
AB - For positive integers a and b, an (a, b̄)-parking function of length n is a sequence (p1, . . ., pn) of nonnegative integers whose weakly increasing order q1 ≤ . . . ≤ qn satisfies the condition qi < a + (i - 1)b. In this paper, we give a new proof of the enumeration formula for (a, b̄)-parking functions by using of the cycle lemma for words, which leads to some enumerative results for the (a, b̄)-parking functions with some restrictions such as symmetric property and periodic property. Based on a bijection between (a, b̄)-parking functions and rooted forests, we enumerate combinatorially the (a, b̄)-parking functions with identical initial terms and symmetric (a, b̄)-parking functions with respect to the middle term. Moreover, we derive the critical group of a multigraph that is closely related to (a, b̄)-parking functions.
KW - Critical group
KW - Cycle lemma
KW - Labeled rooted forest
KW - Parking function
UR - http://www.scopus.com/inward/record.url?scp=77952323085&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77952323085&partnerID=8YFLogxK
U2 - 10.1007/s00373-010-0921-1
DO - 10.1007/s00373-010-0921-1
M3 - Article
AN - SCOPUS:77952323085
VL - 26
SP - 345
EP - 360
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
SN - 0911-0119
IS - 3
ER -