Simple formulas for lattice paths avoiding certain periodic staircase boundaries

DOI10.1016/J.JCTA.2008.05.002MaRDI QIDQ1003635zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Robin Chapman, Timothy Y. Chow, Amit Khetan, David Petrie Moulton, Robert J. Waters

Publication date 4 March 2009

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.2888

zbMATH Keywords

ballot sequencecrossingstairsteptennis balltouchingzigzag

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15)

Abstract: There is a strikingly simple classical formula for the number of lattice paths avoiding the line x = ky when k is a positive integer. We show that the natural generalization of this simple formula continues to hold when the line x = ky is replaced by certain periodic staircase boundaries--but only under special conditions. The simple formula fails in general, and it remains an open question to what extent our results can be further generalized.

Recommendations

• The number of lattice paths below a cyclically shifting boundary
• Counting lattice paths in restricted planes
• Generating functions for lattice paths with several forbidden patterns
• Lattice paths not touching a given boundary
• Koroljuk's formula for counting lattice paths revisited

Cites work

• A solution to the tennis ball problem
• Functional Composition Patterns and Power Series Reversion
• scientific article; zbMATH DE number 1058046 (Why is no real title available?)
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• Lattice paths not touching a given boundary
• Lost (and Found) in Translation: André's Actual Method and Its Application to the Generalized Ballot Problem
• Maintaining the spirit of the reflection principle when the boundary has arbitrary integer slope
• Note on André's reflection principle

Cited in

(6)

• The number of lattice paths below a cyclically shifting boundary
• A Chung-Feller theorem for lattice paths with respect to cyclically shifting boundaries
• scientific article; zbMATH DE number 4077210 (Why is no real title available?)
• Symmetries of statistics on lattice paths between two boundaries
• Two operators on sandpile configurations, the sandpile model on the complete bipartite graph, and a cyclic lemma
• Proof of a lattice paths conjecture connected to the tennis ball problem

This page was built for publication: Simple formulas for lattice paths avoiding certain periodic staircase boundaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003635)