A ``legal'' sequence of parentheses is one in which the parentheses can be properly matched, like ()(()). It's not hard to see that this is possible precisely when the number of left and right parentheses is the same, and every initial segment of the sequence has at least as many left parentheses as right. For example, ())… cannot possibly be extended to a legal sequence. Show that the number of legal sequences of length 2n is Cn=(n2n)−(n+12n). The numbers Cn are called the Catalan numbers.