Number of Valid Parenthesizations:
Given an integer n, write a function f(n) that counts the number of valid sequences consisting of n parenthesis.
Note that “)()(” and “))((” are not valid.
Examples:
• If n = 1, the number of valid sequences consisting of n parenthesis is 1
()
• If n = 2, the number of valid sequences consisting of n parenthesis is 2:
(())
()()
• If n = 3, the number of valid sequences consisting of n parenthesis is 5:
((()))
(()())
(())()
()(())
()()()
• If n = 4, the number of valid sequences consisting of n parenthesis is 14:
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
• If n = 5, the number of valid sequences consisting of n parenthesis is 42
• If n = 6, the number of valid sequences consisting of n parenthesis is 132
• If n = 7, the number of valid sequences consisting of n parenthesis is 429
• If n = 8, the number of valid sequences consisting of n parenthesis is 1430
• If n = 17, the number of valid sequences consisting of n parenthesis is 129644790
• If n = 18, the number of valid sequences consisting of n parenthesis is 477638700
• If n = 19, the number of valid sequences consisting of n parenthesis is 1767263190
I know that the function is recursive. However, I have tried several patterns to come up with the right function but couldn't get it right. Any suggestions or tips to come up with the right pattern?
How does one derive an answer to this?
Write $n_k$ for the number of possible sequences with $k$ pairs. Then $$n_{k+1} = \sum_{i=0}^k n_i n_{k-i}$$
Indeed, we may have between $0$ and $k$ parenthesis-pairs within the first pair; label the number of such pairs $i$. They may appear in $n_i$ ways inside the first pair of parentheses. Then the remaining $k-i$ pairs must all be outside that first pair and form a new string, and this can be done in $n_{k-i}$ ways.
Wikipedia's page on the Catalan numbers tells you how to manipulate this sum once you've got it, but this is how you could have come up with the recurrence in the first place.