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.