A solution to the tennis ball problem

DOI10.1016/J.TCS.2005.08.017MaRDI QIDQ2581346zbMATH OpenOpenAlexFDO

Authors Anna de Mier, Marc Noy

Publication date 10 January 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0311242, http://hdl.handle.net/2117/11950

zbMATH Keywords

Kernel methodLattice pathMatroidsTutte polynomial

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: We present a complete solution to the so-called tennis ball problem, which is equivalent to counting lattice paths in the plane that use North and East steps and lie between certain boundaries. The solution takes the form of explicit expressions for the corresponding generating functions. Our method is based on the properties of Tutte polynomials of matroids associated to lattice paths. We also show how the same method provides a solution to a wide generalization of the problem.

Recommendations

• The tennis ball problem
• On the tennis ball problem
• A Motzkin variation on the tennis ball problem.
• The soccer-ball problem
• A Note on the Tennis Ball Theorem
• Solution of a Ball-Murat problem
• scientific article; zbMATH DE number 2114476
• Rolling ball problems
• High-dimensional tennis balls

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• Generating functions for generating trees
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1300641 (Why is no real title available?)
• scientific article; zbMATH DE number 1156613 (Why is no real title available?)
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• The kernel method: a collection of examples
• The tennis ball problem
• Walks in the quarter plane: Kreweras' algebraic model

Cited in

(19)

• Simple formulas for lattice paths avoiding certain periodic staircase boundaries
• Lattice and Schröder paths with periodic boundaries
• The number of lattice paths below a cyclically shifting boundary
• Delta-matroids as subsystems of sequences of Higgs lifts
• Two-boundary lattice paths and parking functions
• Lattice path matroids: structural properties
• Polynomial equations with one catalytic variable, algebraic series and map enumeration
• On the tennis ball problem
• On Removing a Ball without Disturbing the Others
• Lattice paths with periodic boundaries
• Exactly solved models
• Dénombrements de chemins dans $\mathbb {R}^2$ soumis à contraintes
• Set-valued tableaux and generalized Catalan numbers
• scientific article; zbMATH DE number 2114476 (Why is no real title available?)
• A Motzkin variation on the tennis ball problem.
• Lattice path matroids: the excluded minors
• The tennis ball problem
• Proof of a lattice paths conjecture connected to the tennis ball problem
• A history and a survey of lattice path enumeration

This page was built for publication: A solution to the tennis ball problem

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