next up previous
Next: About this document ... Up: Lecture Notes Previous: Wednesday, May 3, 2000

Unofficial notes on counting parentheses

Counting Parentheses

Now we return to a problem from the very beginning of the course.
In how many ways can a sum of n terms be fully parenthesized?

For each n, we define C(n) as the number of ways in which terms
linked by n + signs  can be fully parenthesized.

C(0) = 1          (no parentheses at all)
C(1) = 1          (a+b)
C(2) = 2 = C(0)*C(1) + C(1)*C(0)         ((a+b)+c)  (a+(b+c))
C(3) = 5 = C(0)*C(2)+C(1)*C(1)+C(2)*C(0)
C(4) = 14 = C(0)*C(3) + C(2)*C(1) + C(1)*C(2) + C(0)*C(3)

Notice the complex recurrence relation,

C(n+1) = Sigma{i < n+1}C(i)*C((n-i)

which is easily deduced from reasoning about the groupings on each
side of the ``top plus sign'' in each position where the ``top plus
sign can appear.

a+(b+(c)) a+(b)+(c)

Group to the left (omit redundant parentheses)
then add parentheses around each rightmost number

Does this preserve the count of parentheses?

each sequence a+b+c+d has n-1 parens added, which is exactly the number
we have omitted in rewriting it this way!

Such an expression is a well-formed sequence of n pairs of parentheses,
in which each parenthesis is matched by a following closing parenthesis.

Some such sequences are bad -- we don't like )(  or ())(

When we scan a sequence of parentheses, we discover it is bad
at the first point where the number of right parentheses
exceeds the number of left parentheses (so at the previous point
the number of left and right parentheses are equal).

We perform the following transformation on bad sequences:
reverse the direction of each parenthesis up to and including
the first bad one.  The effect on the parenthesis count is
to convert one right parenthesis to a left parenthesis -- we
get a sequence with n+1 left parentheses and n-1 right parentheses.

Here's the cute part: this map is a bijection.  The number of bad
sequences of n lefts and n rights is exactly equal to the number of
sequences of n+1 rights.  To reverse the transformation, take any
sequence of n+1 lefts and n-1 rights and go up to the first point
at which the number of lefts exceeds the number of rights -- there must
be such a point because there are more lefts at the end!  Reverse up
to that point and you obtain a uniquely determined bad sequence of
n lefts and  n rights.

The number of sequences (good and bad) of n lefts and n rights is
C(2n,n) (choose the positions for the n lefts); the number of bad
sequences with n lefts and n rights = the number of sequences with
n+1 lefts and n-1 rights = C(2n,n+1).  Thus the number of good
sequences = C(n) = C(2n,n) - C(2n,n+1).

Since C(2n,n+1) = C(2n,n)*((2n-n)/(n+1)) = C(2n)*(n/(n+1)),
we have the following

Theorem:  C(n) = C(2n,n)/(n+1)

Components:

clever bijection number one:  from the usual arrangements of letters,
plus signs and parentheses to mere arrangements of parentheses

clever bijection number two:  from the bad sequences of n lefts and n rights
to all sequences of n+1 lefts and n-1 rights.



Randall Holmes
2000-05-05