20.4. Valid Strings of Parentheses

Try these first

1. 1.

   How many valid strings can we form with 2 pairs of parentheses?

   Hint

   Draw out the pairs to visualize options.

2. 2.

   If n equals 1, how many valid parenthesis strings are possible?

   Hint

   Consider what it takes to open and close a bracket.

3. 3.

   How many valid strings can be formed with 3 pairs of parentheses?

   • 3
   • 5
   • 12

   Hint

   Use the formula of Catalan numbers.

4. 4.

   C(n) represents the number of valid parenthesis for n pairs. True or False?

   • True
   • False

   Hint

   Think about the scenarios imagined in class.

5. 5.

   Prove that the nth Catalan number can be also expressed as C(2n, n)/(n+1).

   Hint

   Think combinatorically about choices of pairs in arrangements.

6. 6.

   How many unique valid arrangements can you create with 5 pairs of parentheses?

   Hint

   You can calculate using the recurrence relation iteratively.