21.1.1. Recap of Previous Lecture

Try these first

1. 1.

   What is the formula for Catalan numbers?

   Hint

   Think about the number of valid structures divided by n+1.

2. 2.

   How many valid parenthesis combinations are there for n = 2?

   Hint

   Try to visualize the arrangements.

3. 3.

   What are Catalan numbers commonly used to count?

   • Valid sequences of parentheses
   • Prime numbers
   • Fibonacci sequences

   Hint

   Think about the structures you’ve learned.

4. 4.

   True or False: The number of valid sequences of 1s and -1s equals the number of valid parentheses strings.

   • True
   • False

   Hint

   Refer to the connections discussed.

5. 5.

   Prove that the number of valid parenthesis sequences increases exponentially as n rises.

   Hint

   Reflect on how factorial numbers grow.

6. 6.

   If you add a ‘bad’ sequence to a valid sequence, what type of sequence is produced?

   Hint

   Check how the sums behave post addition.