# A solution to the tennis ball problem

@article{Mier2005AST, title={A solution to the tennis ball problem}, author={Anna de Mier and Marc Noy}, journal={Theor. Comput. Sci.}, year={2005}, volume={346}, pages={254-264} }

We present a complete solution to the so-called tennis ball problem, which is equivalent to counting the number of 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.

#### 28 Citations

Proof of a Lattice Paths Conjecture Connected to the Tennis Ball Problem

- Mathematics
- 2010

We give a short history of the so-called tennis ball problem, and discuss its relation to lattice path enumeration. We also prove a conjecture related to a solution of the symmetric case, namely when… Expand

Simple formulas for lattice paths avoiding certain periodic staircase boundaries

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2009

It is shown 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. Expand

Exactly solved models of polyominoes and polygons

- Mathematics
- 2008

This chapter deals with the exact enumeration of certain classes of selfavoiding polygons and polyominoes on the square lattice. We present three general approaches that apply to many classes of… Expand

Lattice path matroids: The excluded minors

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2010

The minor-closed class of lattice path matroids is characterized by its excluded minors by means of a presentation for which some antichain of intervals in some linear order on the ground set is a presentation. Expand

Lattice path matroids: Structural properties

- Computer Science, Mathematics
- Eur. J. Comb.
- 2006

One of the main results is a characterization of lattice path matroids in terms of fundamental flats, which are special connected flats from which one can recover the paths that define the matroid. Expand

The number of lattice paths below a cyclically shifting boundary

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2009

This work counts the number of lattice paths lying under a cyclically shifting piecewise linear boundary of varying slope and recovers known expressions concerning paths dominated by a line of half-integer slope, and some new and old formulae for paths lyingunder special ''staircases. Expand

Two-boundary lattice paths and parking functions

- Mathematics, Computer Science
- Adv. Appl. Math.
- 2007

We describe an involution on a set of sequences associated with lattice paths with north or east steps constrained to lie between two arbitrary boundaries. This involution yields recursions (from… Expand

A Natural Family of Flag Matroids

- Computer Science, Mathematics
- SIAM J. Discret. Math.
- 2007

This paper gives a family of flag matroids arising from an enumeration problem that is a generalization of the tennis ball problem and can be defined in terms of lattice paths. Expand

A history and a survey of lattice path enumeration

- Mathematics
- 2010

Abstract In celebration of the Sixth International Conference on Lattice Path Counting and Applications, it is befitting to review the history of lattice path enumeration and to survey how the topic… Expand

Counting Lattice Paths and Walks with Several Step Vectors

- 2014

Many famous researchers in computer science, mathematics and other areas have studied enumerative problems in lattice path and walks which could be applied to many fields. We will discuss some new… Expand

#### References

SHOWING 1-10 OF 17 REFERENCES

The Tennis Ball Problem

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2002

A natural generalization of the s-tennis ball problem is explored, which reduces to that considered by Mallows and Shapiro in the case s =2, and it is shown how this generalization is connected with s -ary trees. Expand

Balls on the Lawn

- Mathematics
- 1999

Abstract: In the "tennis ball" problem we are given successive pairs of balls numbered (1,2), (3,4),... At each stage we throw one ball out of the window. After n stages some set of n balls is on the… Expand

Walks in the quarter plane: Kreweras’ algebraic model

- Mathematics
- 2004

We consider planar lattice walks that start from (0, 0), remain in the first quadrant i, j ≥ 0, and are made of three types of steps: North-East, West and South. These walks are known to have… Expand

Lattice path matroids: enumerative aspects and Tutte polynomials

- Computer Science, Mathematics
- J. Comb. Theory, Ser. A
- 2003

The Tutte polynomials of lattice path matroids can be computed in polynomial time and a new result about lattice paths is obtained from an analysis of the β invariant of certain lattice Path Matroids. Expand

On the enumeration of planar maps

- Mathematics
- 1968

A planar map is determined by a finite connected nonnull graph embedded in the 2-sphere or closed plane. It is permissible for the graph to have loops or multiple joins. It separates the remainder of… Expand

A contribution to the theory of chromatic polynomials

- Mathematics
- 1954

Two polynomials 6(G, n) and <f>(G, n) connected with the colourings of a graph G or of associated maps are discussed. A result believed to be new is proved for the lesser-known polynomial <f>(G, n).… Expand

Generating functions for generating trees

- Computer Science, Mathematics
- Discret. Math.
- 2002

The relationship between structural properties of the rules defining such trees and the rationality, algebraicity, or transcendence of the corresponding generating functions are investigated. Expand

Theoretical Computer Science

- Computer Science
- Lecture Notes in Computer Science
- 2003

The Fully Mixed Nash Equilibrium Conjecture is valid for pure Nash equilibria and that under a certain condition, the social cost of any Nash equilibrium is within a factor of 6 + ε, of that of the fully mixed Nash equilibrium, assuming that link capacities are identical. Expand

Complexity: Knots, Colourings and Counting

- Mathematics
- 1993

1. The complexity of enumeration 2. Knots and links 3. Colourings, flows and polynomials 4. Statistical physics 5. Link polynomials 6. Complexity questions 7. The complexity of uniqueness and parity… Expand

THE KERNEL METHOD: A COLLECTION OF EXAMPLES

- 2003

The kernel method has recently become quite popular. Roughy speaking, in certain cases one obtains for a multivariate generating function a functional equation. For certain couplings of the… Expand