Cycle lemma, parking functions and related multigraphs

Sen-Peng Eu, Tung Shan Fu, Chun Ju Lai

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)345-360
Number of pages16
JournalGraphs and Combinatorics
Volume26
Issue number3
DOIs
Publication statusPublished - 2010 Mar 8

Fingerprint

Parking Functions
Multigraph
Parking
Bijection
Lemma
Cycle
Critical Group
Integer
Term
Enumeration
Non-negative
Restriction

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 journalArticle

Eu, Sen-Peng ; Fu, Tung Shan ; Lai, Chun Ju. / Cycle lemma, parking functions and related multigraphs. In: Graphs and Combinatorics. 2010 ; Vol. 26, No. 3. pp. 345-360.
@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 = "Sen-Peng Eu and Fu, {Tung Shan} and Lai, {Chun Ju}",
year = "2010",
month = "3",
day = "8",
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

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 -