Refined Chung-Feller theorems for lattice paths

Sen Peng Eu, Tung Shan Fu, Yeong Nan Yeh

Research output: Contribution to journalArticle

15 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 languageEnglish
Pages (from-to)143-162
Number of pages20
JournalJournal of Combinatorial Theory. Series A
Volume112
Issue number1
DOIs
Publication statusPublished - 2005 Oct 1

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

Fingerprint Dive into the research topics of 'Refined Chung-Feller theorems for lattice paths'. Together they form a unique fingerprint.

  • Cite this