Cycle Lemma, Parking Functions and Related Multigraphs |
| |
Authors: | Sen-Peng Eu Tung-Shan Fu Chun-Ju Lai |
| |
Affiliation: | 1. Department of Applied Mathematics, National University of Kaohsiung, Kaohsiung, 811, Taiwan, ROC 2. Mathematics Faculty, National Pingtung Institute of Commerce, Pingtung, 900, Taiwan, ROC 3. Department of Electrical Engineering, National Taiwan University, Taipei, 106, Taiwan, ROC
|
| |
Abstract: | For positive integers a and b, an ${(a, overline{b})}$ -parking function of length n is a sequence (p 1, . . . , p n ) of nonnegative integers whose weakly increasing order q 1 ≤ . . . ≤ 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, overline{b})}$ -parking functions by using of the cycle lemma for words, which leads to some enumerative results for the ${(a, overline{b})}$ -parking functions with some restrictions such as symmetric property and periodic property. Based on a bijection between ${(a, overline{b})}$ -parking functions and rooted forests, we enumerate combinatorially the ${(a, overline{b})}$ -parking functions with identical initial terms and symmetric ${(a, overline{b})}$ -parking functions with respect to the middle term. Moreover, we derive the critical group of a multigraph that is closely related to ${(a, overline{b})}$ -parking functions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|