Mathematics for Computer Science

15.6. References 657

of various recursively defined sets—there are in fact hundreds of interpretations of
these numbers!^6
We are only going to look at one that is relevant to a familiar recursively defined
set RecMatch of strings of matched brackets given in Definition 6.2.1.
Thenth Catalan number,cn, is equal to the number of strings in RecMatch hav-
ing exactlynleft brackets.
Note thatc 0 D 1 sinceis the only string in RecMatch with 0 left brackets.
(a)Find a recursive definition forcnin terms ofc 0 ;c 1 ;:::cn 1 forn 1. (Hint:
assumingsandtare in RecMatch, what are the possible pairs of integers describ-
ing the numbers of left brackets in each such that[ ]has exactlynleft brackets in
total?)

(b)Show that the generating functionC.x/corresponding tohc 0 ;c 1 ;c 2 ;:::isat-
isfies the following equation

C.x/D 1 CxC.x/^2 : (15.24)

Solving forC.x/in (15.24) shows that one of the two possible generating functions
corresponding to the Catalan numbers is

C.x/D

1

p

1 4x

2x

(c)Use this generating function to show that

cnD

1

nC 1

2n

n

!

forn 0.

Hint:It may be easier to find a closed form for the coefficientŒxnç2xC.x/first.

Problem 15.19.
Generating functions provide an interesting way to count the number of strings of
matched brackets. To do this, we’ll use a description of these strings as the set,
GoodCount, of strings of brackets with a good count.^7
Namely, one precise way to determine if a string is matched is to start with 0
and read the string from left to right, adding 1 to the count for each left bracket

(^6) http://www-math.mit.edu/ rstan/ec/catadd.pdf
(^7) Problem 6.16 also examines these strings.