Questions: Catalan Numbers and Recursive Structures

Question 1

You want to count the number of ways to triangulate a convex polygon with 5 vertices. A classmate argues the answer is 5! = 120, since there are 5 vertices and they can be chosen in any order. Which response best explains the error?

• A. The classmate is right — 5! counts all valid triangulations of a pentagon
• B. The answer is C₃ = 5, because every triangulation decomposes by choosing a triangle containing the base edge, splitting the remaining vertices into two independent sub-problems
• C. The answer is 2ⁿ because each diagonal is either included or excluded
• D. The classmate's formula is wrong because vertices are indistinguishable, so we divide by 5

Answer: (B)

The triangulation count is C₃ = 5, not 5!. The key is the Catalan recursive decomposition: pick a fixed base edge; the triangle that contains it splits the remaining vertices into two groups of sizes i and n−1−i for all valid i. Each group is independently triangulated, giving the Catalan recurrence Cₙ = ΣCᵢCₙ₋₁₋ᵢ. Factorial counting applies to ordered selections without this recursive structure. Recognizing the decomposition — not the combinatorial object itself — is what identifies a Catalan problem.

Question 2

The generating function C(x) for Catalan numbers satisfies the equation xC(x)² − C(x) + 1 = 0. Why does the generating function satisfy a *quadratic* equation rather than a linear one?

• A. Because C₀ = 1 and C₁ = 1 are both equal to 1, introducing quadratic symmetry
• B. Because the Catalan recurrence is a convolution of two copies of the Catalan sequence, which corresponds to a product C(x)·C(x) in generating function language
• C. Because Catalan numbers grow quadratically in magnitude
• D. Because the closed form involves a square root, which always produces a quadratic equation

Answer: (B)

The Catalan recurrence Cₙ = Σᵢ CᵢCₙ₋₁₋ᵢ is a self-convolution: each term is a product of two Catalan numbers. In generating function language, a convolution of a sequence with itself corresponds to [C(x)]², so the recurrence translates to C(x) = 1 + xC(x)², a quadratic in C(x). This is the power of generating functions: the infinite tower of recurrence relations collapses into a single algebraic equation whose solution gives the closed form.

Question 3

The unifying reason Catalan numbers appear in counting binary trees, parenthesizations, and non-crossing matchings is that all these objects share the same recursive decomposition structure, not surface-level similarity.

• T. True
• F. False

Answer: True

This is precisely the key insight. A balanced parenthesization, a full binary tree, a non-crossing handshake pattern — these look nothing alike geometrically, but all share the same decomposition: there is always a 'first' element that splits the remaining structure into two independent sub-problems of complementary sizes i and n−1−i. This shared recurrence Cₙ = ΣCᵢCₙ₋₁₋ᵢ is why the same numbers appear. Recognizing the decomposition is how you identify a Catalan problem in a new context.

Question 4

If a combinatorial problem produces the sequence 1, 2, 5, 14, 42, ... for n = 1, 2, 3, 4, 5, that is sufficient evidence that the problem is a Catalan number problem.

• T. True
• F. False

Answer: False

Matching the numerical sequence is suggestive but not sufficient. A problem is a Catalan problem if and only if its objects admit the correct recursive decomposition: a 'first element' that splits the rest into two independent sub-problems of all possible complementary sizes. Different problems can coincidentally produce the same counts for small n but diverge later, or be Catalan for the wrong reason. Verifying the structural decomposition — deriving the recurrence from the combinatorial definition — is the rigorous check.

Question 5

Why does the Catalan recurrence Cₙ = Σᵢ₌₀ⁿ⁻¹ CᵢCₙ₋₁₋ᵢ involve a *product* of two Catalan numbers in each term, rather than a sum?

Model answer: Because the decomposition creates two *independent* sub-problems. When you split a structure at its 'first element,' the left part (of size i) and the right part (of size n−1−i) can each be arranged in any valid way without affecting the other. By the multiplication principle, the number of combined arrangements is the product of the counts for each part separately. Summing over all possible split points i gives the recurrence. If the two parts were not independent — if choices in one constrained choices in the other — a product would not be appropriate.

The independence of the two sub-problems is what makes the product form correct. This is the multiplication principle of counting: if event A can occur in m ways and independent event B can occur in k ways, the pair (A, B) can occur in m·k ways. Each Catalan term CᵢCₙ₋₁₋ᵢ counts all combinations of a left sub-structure and a right sub-structure independently. Summing over i collects all possible split positions. This structure — a sum of products of two Catalan sequences — is exactly what produces the self-convolution and the quadratic generating function equation.