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

## Balls on the Lawn

### Colin L. Mallows 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.

## 1. Introduction.

The tennis ball problem goes as follows. At the first turn you are given balls numbered 1 and 2. You throw one of them out the window onto the lawn. At the second turn balls numbered 3 and 4 are brought in and now you throw out on the lawn any of the three balls in the room with you. Then balls 5 and 6 are brought in and you throw out one of the four available balls. The game continues for n turns. The first question is how many different arrangements on the lawn are possible. It is easy to see that there are 2, 5 and 14 possibilities after 1, 2 and 3 turns. This suggests the Catalan numbers which turns out to be the case. A more delicate question is "what is the total sum of the balls on the lawn over all these possibilities"? Here the first few terms are 3, 23, 131 and 664. As an example consider the five possibilities after two turns. They are , , , or .The total sum is .

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 ). 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 ,, or  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  and  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 U, if neither is selected mark with a D, if the odd member is the one selected use an L, if the even number was selected then use an l. This sets up an obvious correspondence with the bicolored Motzkin paths ending at height zero and this shows that the number of possibilities after n turns is the Catalan number Cn+1.

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 2n+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.

## 2. Definitions and notation.

The nth Catalan number is .The generating function for the sequence of Catalan numbers is where Q= .Similarly is the generating function for the sequence of central binomial coefficients.

The following lemmas can be proved combinatorially but instead we refer to Concrete Mathematics , 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.

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 n=m+i and then i=j+d we obtain  We sum on m first; then invoke Lemma 2. By rewriting 2j+d=2j+d+1-1 we get where and However, with the aid of Lemmas 3 and 4, we obtain For the second term we have, via Lemmas 2 and 4, Thus ## 3. Remarks.

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: since Q2=1-4z. But while .Thus extracting nth terms yields Two 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  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 , who refers to the logic text  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.

## References

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 Journal of Integer Sequences home page