Cycle lemma, parking functions and related multigraphs

Sen Peng Eu; Tung Shan Fu; Chun Ju Lai

doi:10.1007/s00373-010-0921-1

Cycle lemma, parking functions and related multigraphs

Sen Peng Eu, Tung Shan Fu, Chun Ju Lai

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

For positive integers a and b, an (a, b̄)-parking function of length n is a sequence (p₁, . . ., p_n) of nonnegative integers whose weakly increasing order q₁ ≤ . . . ≤ q_n satisfies the condition q_i < 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	https://doi.org/10.1007/s00373-010-0921-1
Publication status	Published - 2010

Keywords

Critical group
Cycle lemma
Labeled rooted forest
Parking function

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-010-0921-1

Cite this

@article{f939621c635441c2a02bf8fce4033186,

title = "Cycle lemma, parking functions and related multigraphs",

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.",

keywords = "Critical group, Cycle lemma, Labeled rooted forest, Parking function",

author = "Eu, {Sen Peng} and Fu, {Tung Shan} and Lai, {Chun Ju}",

note = "Funding Information: S.-P. Eu is partially supported by National Science Council (NSC), Taiwan under grant 98-2115-M-390-002-MY3. T.-S. Fu is partially supported by NSC under grant 97-2115-M-251-001-MY2.",

year = "2010",

doi = "10.1007/s00373-010-0921-1",

language = "English",

volume = "26",

pages = "345--360",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "3",

}

TY - JOUR

T1 - Cycle lemma, parking functions and related multigraphs

AU - Eu, Sen Peng

AU - Fu, Tung Shan

AU - Lai, Chun Ju

N1 - Funding Information: S.-P. Eu is partially supported by National Science Council (NSC), Taiwan under grant 98-2115-M-390-002-MY3. T.-S. Fu is partially supported by NSC under grant 97-2115-M-251-001-MY2.

PY - 2010

Y1 - 2010

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 -

Cycle lemma, parking functions and related multigraphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this