Exercise · ZW-CATALAN-NUMBER-005 · ★★☆ Intermediate
Which of the following expressions equals \(C_n\)?
Choose one option.
Show answer
- B. \(\binom{2n}{n}-\binom{2n}{n+1}\)
Explanation
By the reflection principle, subtracting \(\binom{2n}{n+1}\) from \(\binom{2n}{n}\) gives \(C_n\); for \(n=2\) it gives \(6-4=2\). The other expressions do not match \(C_n\) for \(n=1\) or \(n=2\).
Review the concept: Catalan number
The Catalan number \(C_n\) counts, among many other structures, the triangulations of a convex polygon with \(n+2\) sides and the Dyck paths of length \(2n\).
\[C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{n!\,(n+1)!}\]
More practice problems: catalan number
- ZW-CATALAN-NUMBER-001 What is the value of C_2?
- ZW-CATALAN-NUMBER-002 What is the value of C_0?
- ZW-CATALAN-NUMBER-003 How many distinct triangulations does a convex hexagon have, using diagonals that do not cross in i…
- ZW-CATALAN-NUMBER-004 In how many different ways can the product x_1x_2x_3 be parenthesized?
- ZW-CATALAN-NUMBER-006 Compute C_4 using the recurrence C_n+1=∑_k=0^n C_k C_n-k with C_0=1, C_1=1, C_2=2, C_3=5.
- ZW-CATALAN-NUMBER-007 Compute binom105 and use it to find C_5 through C_n=(1)/(n+1)binom2nn.
- ZW-CATALAN-NUMBER-008 Compute (C_n+1)/(C_n) for n=3 from C_3=5 and C_4=14.
- ZW-CATALAN-NUMBER-009 How many Dyck paths of length 6 exist?