|Journal of Integer Sequences, Vol. 2 (1999), Article 99.1.5|
Washington, DC 20059
Email address: firstname.lastname@example.org
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.
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.
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.
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
However, with the aid of Lemmas 3 and 4, we obtain
For the second term we have, via Lemmas 2 and 4,
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.
Received July 17, 1998; revised version received Jan 13, 1999. Published in Journal of Integer Sequences March 15, 1999.