GATE CS 1990 Q3-iii — Combinatorics: Counting, Recurrence Relations, Generating Functions

The number of unlabeled rooted binary trees with $n$ nodes is given by the $n$-th Catalan number, denoted as $C_n$.

The formula for the $n$-th Catalan number is:

Let's evaluate each option based on this definition:

• Option A: The number of ways to fully parenthesize (multiply) a chain of $k$ matrices is given by the Catalan number $C_{k-1}$. For $k = n+1$ matrices, the number of ways is $C_{(n+1)-1} = C_n$. Thus, this option is correct.
• Option B: The number of ways of arranging $n$ out of $2n$ distinct elements is given by the permutation $P(2n, n) = \frac{(2n)!}{n!}$, which is not equal to $C_n$. Thus, this option is incorrect.
• Option C: This is the exact algebraic expression for the $n$-th Catalan number $C_n$. Thus, this option is correct.
• Option D: The value $n!$ grows much faster than $C_n$ for larger $n$ (for example, for $n=3$, $C_3 = 5$ but $3! = 6$). Thus, this option is incorrect.