Refined Chung-Feller theorems for lattice paths

Sen Peng Eu; Tung Shan Fu; Yeong Nan Yeh

doi:10.1016/j.jcta.2004.11.016

Refined Chung-Feller theorems for lattice paths

Sen Peng Eu^*, Tung Shan Fu, Yeong Nan Yeh

^*Corresponding author for this work

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

22 Citations (Scopus)

Abstract

In this paper we prove a strengthening of the classical Chung-Feller theorem and a weighted version for Schröder paths. Both results are proved by refined bijections which are developed from the study of Taylor expansions of generating functions. By the same technique, we establish variants of the bijections for Catalan paths of order d and certain families of Motzkin paths. Moreover, we obtain a neat formula for enumerating Schröder paths with flaws.

Original language	English
Pages (from-to)	143-162
Number of pages	20
Journal	Journal of Combinatorial Theory. Series A
Volume	112
Issue number	1
DOIs	https://doi.org/10.1016/j.jcta.2004.11.016
Publication status	Published - 2005 Oct
Externally published	Yes

Keywords

Catalan paths
Chung-Feller theorem
Generating function
Motzkin paths
Schröder paths
Taylor expansion

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jcta.2004.11.016

Cite this

@article{b990a8019c634fda8772e8c7c3522cf0,

title = "Refined Chung-Feller theorems for lattice paths",

abstract = "In this paper we prove a strengthening of the classical Chung-Feller theorem and a weighted version for Schr{\"o}der paths. Both results are proved by refined bijections which are developed from the study of Taylor expansions of generating functions. By the same technique, we establish variants of the bijections for Catalan paths of order d and certain families of Motzkin paths. Moreover, we obtain a neat formula for enumerating Schr{\"o}der paths with flaws.",

keywords = "Catalan paths, Chung-Feller theorem, Generating function, Motzkin paths, Schr{\"o}der paths, Taylor expansion",

author = "Eu, {Sen Peng} and Fu, {Tung Shan} and Yeh, {Yeong Nan}",

note = "Funding Information: E-mail addresses: [email protected] (S.-P. Eu) , [email protected] (T.-S. Fu) , [email protected] (Y.-N. Yeh) . 1 Partially supported by National Science Council, Taiwan, R.O.C. (NSC 92-2119-M-390-001). 2 Partially supported by National Science Council, Taiwan, R.O.C. (NSC 92-2115-M-251-001). 3 Partially supported by National Science Council, Taiwan, R.O.C. (NSC 92-2115-M-001-016).",

year = "2005",

month = oct,

doi = "10.1016/j.jcta.2004.11.016",

language = "English",

volume = "112",

pages = "143--162",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Refined Chung-Feller theorems for lattice paths

AU - Eu, Sen Peng

AU - Fu, Tung Shan

AU - Yeh, Yeong Nan

N1 - Funding Information: E-mail addresses: [email protected] (S.-P. Eu) , [email protected] (T.-S. Fu) , [email protected] (Y.-N. Yeh) . 1 Partially supported by National Science Council, Taiwan, R.O.C. (NSC 92-2119-M-390-001). 2 Partially supported by National Science Council, Taiwan, R.O.C. (NSC 92-2115-M-251-001). 3 Partially supported by National Science Council, Taiwan, R.O.C. (NSC 92-2115-M-001-016).

PY - 2005/10

Y1 - 2005/10

N2 - In this paper we prove a strengthening of the classical Chung-Feller theorem and a weighted version for Schröder paths. Both results are proved by refined bijections which are developed from the study of Taylor expansions of generating functions. By the same technique, we establish variants of the bijections for Catalan paths of order d and certain families of Motzkin paths. Moreover, we obtain a neat formula for enumerating Schröder paths with flaws.

AB - In this paper we prove a strengthening of the classical Chung-Feller theorem and a weighted version for Schröder paths. Both results are proved by refined bijections which are developed from the study of Taylor expansions of generating functions. By the same technique, we establish variants of the bijections for Catalan paths of order d and certain families of Motzkin paths. Moreover, we obtain a neat formula for enumerating Schröder paths with flaws.

KW - Catalan paths

KW - Chung-Feller theorem

KW - Generating function

KW - Motzkin paths

KW - Schröder paths

KW - Taylor expansion

UR - http://www.scopus.com/inward/record.url?scp=25144510112&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=25144510112&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2004.11.016

DO - 10.1016/j.jcta.2004.11.016

M3 - Article

AN - SCOPUS:25144510112

SN - 0097-3165

VL - 112

SP - 143

EP - 162

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

IS - 1

ER -

Refined Chung-Feller theorems for lattice paths

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this