Unknown

262 Answers to Exercises and Solutions to Problems

If T = 1, there are f(n - 1) ways of choosing al,... ,a,-1 to satisfy

inequalities (C). If T = n, the re are j(n - 1) ways of choosing al,... ,a,-1

to satisfy (A) (in th’ is case, a, = 0 and al is determined by the last line).

If 1 < T < n, there are f(r - 1) ways of satisfying (A) and f(n - r) ways

of satisfying (C). H ence, with the convention that f(0) = 1,

n-1

f(n) = C f(r)f(n - I- +

r=O

To find a closed form for f(n), we make use of a generating function. Let

y be the formal power series defined by

y = 1+ f(l)x + f(2)x2 + f(3)x3 +.. *

= 1 + 1: + 2x2 + 5x3 + 14x4 + 42x5 +....

Then, with the recursion relation taken into account, it can be checked that

XY2 -y+l=O.

Solving this equation for y yields

Y=

1 - (1 - 4x)1/2

2x *

Expanding the right-hand side binomially, we find that

m,=g n$)=&( ?)=A( ,,,,).

This problem is E2972 posed in the American Mathematical Monthly 89
(1982), 698. A solution with reference appears in the Amer. Math. Monthly
93 (1986), 217-218.
Note: The numbers 1, 1, 2, 5, 14, 42, 132, 429,... , f(n - l),... are called
the Catalan numbers. An article in Scientific American (June, 1976; pages
120-125) draws attention to a number of interesting properties and inter-
pretations. Euler showed that the nth term is the number of ways a fixed
convex polygon with n + 1 vertices can be decomposed by diagonals into
nonoverlapping triangles. Catalan interpreted the nth term as the number
of ways a chain of n letters in fixed order can be equipped with n - 1 pairs
of parentheses so that two terms reside between a corresponding pair. For
example, when n = 4, we have

I am indebted to W. Karpinski for the observation that

[

f(n - l)f(n - 2)

’ + 24 f(n)f(n - 2) - f(n - 1)2 1 = (2n + ‘I”