Guichard-Combinatorics-Graph-Theory · Problem 3.5.3

Generating Functions

Mathematics — Probability · catalan-numbers-parentheses

Problem

Show that if AnA_n is the number of properly matched sequences of parentheses of length 2n2n, then An=∑i=0n−1AiAn−i−1.A_n = \sum_{i=0}^{n-1} A_i A_{n-i-1}. Do this in the same style that we used for the number of rooted binary trees: Given all the sequences of shorter length, explain how to combine them to produce the sequences of length 2n2n, in such a way that the sum clearly counts the number of sequences. Hint: Prove the following lemma: If ss is a properly matched sequence of parentheses of length 2n2n, ss may be written uniquely in the form (s1)s2(s_1)s_2, where s1s_1 and s2s_2 are properly matched sequences of parentheses whose lengths add to 2n−22n-2. For example, (())()=([()])[()](())() = ([()])[()] and ()(())=([])[(())]()(()) = ([])[( ())], with the sequences s1s_1 and s2s_2 indicated by [  ][\;]. Note that s1s_1 and s2s_2 are allowed to be empty sequences, with length 0.

Related theory

Browse the problem library