Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.5 |

AT&T Research Labs

180 Park Avenue

Florham Park, NJ 07932

Email address: clm@research.att.com

Lou Shapiro

Math Dept.

Howard University

Washington, DC 20059

Email address: lws@scs.howard.edu

**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 lawn. We find
a generating function and a closed formula for the sequence
3,23,131,664,3166,14545,65187,287060,1247690,...,
the *n*-th term of which gives the sum over all possible arrangements of
the total of the numbers on the balls on the lawn. The problem has
connections with "bicolored Motzkin paths" and the ballot problem.

We will find both a generating function and a closed formula for this sequence. First we return to the first question and transform it to a question about paths.

- Consider paths in the plane which satisfy the following conditions:
- The possible steps are , and .We allow the level steps
to be
one of two colors,
*L*or*l*. - The paths start at and consist of
*n*steps. - The paths never go below the
*x*-axis.Such paths are called

**bicolored Motzkin paths**(see [5]). If there had been only one kind of level step and the paths ended on the*x*-*axis*we would have regular Motzkin paths (see [1],[3], or [7] for more information on Motzkin paths and Motzkin numbers).

Let be the number of possible paths that end at . Here is a table of small values

We can make three observations. One is that with the four kinds of steps we get the recursion

This holds for if we specify that and . Both conditions make sense in terms of these paths.Secondly we have

Given the recursion, this is easily established by induction.Thirdly the Catalan number (see [6] and [7] for different proofs).

Now we return to the balls on the lawn after turns. Let us look at a typical example after 6 turns.

The balls on the lawn are denoted by "". As we read from left to right one pair at a time, we must always have as many or more pairs with both balls selected as with no balls selected with equality at the end. If both balls are selected mark the pair with a
We now want to shift back to subdiagonal paths from
to using unit east and north steps. If we number
the
steps along each such path starting at the origin using the numbers
to 2*n*+1, then the numbers of the horizontal steps correspond to the
numbers of
the balls on the lawn except that we ignore the initial horizontal step
numbered 0. All subdiagonal paths must go from to
at the first step so let us look on as our starting point and as the terminal point.
We
then look at steps in pairs to set up a correspondence with bicolored
Motzkin paths

To evaluate the sum over all possible sets of balls on the lawn takes a bit more doing and its worthwhile to separate out some definitions and lemmas first.

The following lemmas can be proved combinatorially but instead we refer to Concrete Mathematics [4], page 203, formulas and for the first two lemmas and leave the others as exercises.

**Lemma 1**

**Lemma 2**

**Lemma 3**

**Lemma 4**

**Lemma 5**

**Lemma 6**

**Lemma 7**

The number of subdiagonal paths from to will be denoted and

This is the cornerstone result about ballot numbers and a reference which summarizes this and much of the related literature is[2].We now want to embark on the main computation. Note first that

Before launching into the evaluation lets look at each term. There are
paths from to and paths from to
.What does it mean for a path to have arrived at
?
Of the balls , *i*-1
of them are on the lawn and *j* of them are to stay in the room.
The horizontal
step indicates that
ball number *i*+*j* is to be on the lawn and hence the term .By Lemma 7 we then get

We want to find a closed form for the generating function

If we set- 1.
- 2.
- 3.
- There is also a connection with hypergeometric functions. and

The first and third of these remarks can be shown by routine algebraic manipulations and the second follows from the first as follows:

sinceTwo other remarks can be made here. First, an asymptotic result,

Second, the expected value of the balls on the lawn is if we assume each available ball is equally likely to be picked at each turn.Problem 19(s) of reference [7] is succinct but less colorful. It asks one to show that the Catalan numbers count sequences of positive integers such that and .The references there point out a connection with an indexing of the weights of the fundamental representation of the symplectic group .

The problem was brought to our attention by Ralph Grimaldi, see [6], who refers to the logic text [8] where it is pointed out that after an infinite number of turns the balls remaining in the room can be either the empty set, a finite set of arbitrary size or even an infinite set such as all the even numbered balls.

**1**- Barcucci E., R. Pinzani, & R. Sprugnoli,
The Motzkin family,
*PU.M.A. Ser. A*,**2**(1991) 249-279. **2**- Barton, D. E. & C. L. Mallows, Some aspects of the random sequence,
*Ann. Math. Stat.*,**36**(1965) 236-260. **3**- Donaghey R. & L. W. Shapiro, The Motzkin numbers,
*J. Combinatorial Theory Ser. A*,**23**(1977) 291-301. **4**- Graham R., D. E. Knuth & O. Patashnik,
*Concrete Mathematics*, Addison-Wesley, 1990. **5**- Getu S. & L. Shapiro, Catalan and Motzkin probabilities,
(to appear),
*Congressus Numerantium*. **6**- Grimaldi R. & J. Moser, The Catalan
numbers and the tennis ball problem,
*Congressus Numerantium*,**125**(1997) 65-71. **7**- Stanley, R. P.,
*Enumerative Combinatorics*,*volume 2*, to appear, Cambridge University Press. **8**- Tymoczko T.& J. Henle,
*Sweet Reason: A Field Guide to Modern Logic*, Freeman, 1995, p. 304.

(Concerned with sequence A031970 .)

Received July 17 1998; revised version received January 13 1999. Published in Journal of Integer Sequences March 15 1999.

Return to