21.1. Catalan Numbers - Derivation of Closed Form Formula

Try these first

1. 1.

   Define Catalan numbers in your own words.

   Hint

   Think about their connection to parentheses.

2. 2.

   What is the cardinality of set A?

   Hint

   Recalling the combination formula for selecting positions.

3. 3.

   What is the closed-form formula for the nth Catalan number?

   • C(n) = C(2n
   • n)/(n + 1)
   • C(n) = C(2n
   • n)/n
   • C(n) = C(n + 1
   • 2n)

   Hint

   Look for structure and combinatorial significance.

4. 4.

   True or False: Set B contains all sequences that have only positive partial sums.

   • True
   • False

   Hint

   Focus on the definition provided in the lecture.

5. 5.

   Consider a sequence of n = 4. Calculate the individual possible valid parentheses configurations and show how they relate to C(4, 2).

   Hint

   Try listing them to see how they form.

6. 6.

   Using the reflection method, illustrate how you would transform a bad sequence of n = 2 (for example, 1, -1, 1, -1) to its valid form.

   Hint

   Pay attention to how each sign change results in the surplus.