21.1.4. Proof Strategy

Try these first

1. 1.

   What is the value of C(2, 1)?

   Hint

   Think of the number of ways to choose 1 from 2.

2. 2.

   Define what a bad sequence is in the context of Catalan numbers.

   Hint

   Consider what violates the sequence of valid parenthesis.

3. 3.

   What do Catalan numbers count?

   • Combinations of colors
   • Valid sequences of parentheses
   • Different types of graphs

   Hint

   Think about the nature of matching pairs.

4. 4.

   The reflection method maps bad sequences to valid sequences.

   • True
   • False

   Hint

   Consider how reflection alters the sequences.

5. 5.

   Devise an alternate proof for the formula for Catalan numbers without using the reflection method.

   Hint

   Focus on how smaller sequences of parentheses can combine to form larger ones.

6. 6.

   Calculate C(2n, n) for n = 4 and explain how it relates to Catalan numbers.

   Hint

   Don't forget to apply the formula for C(2n, n) directly!