Catalan numbers: ways to balance 3 pairs of brackets
Need a hint?
List them: ((())), (()()), (())(), ()(()), ()()(). Then check the formula.
There are C₃ = 5 ways to match 3 pairs of brackets; in general C_n = (1/(n+1))·C(2n, n).
How to work it out
The correct arrangements for 3 pairs are
(1)That is five. The formula for pairs is the Catalan number, :
(2)The sequence goes 1, 1, 2, 5, 14, 42, 132, … The same numbers count triangulations of a polygon, paths that stay below a diagonal, and binary trees.
LaTeX source of the formulas on this page
\[ 5 \]
\[ ((())),\ (()()),\ (())(),\ ()(()),\ ()()() \]
\[ C_3=\frac14\binom63=\frac{20}{4}=5 \]Questions
What is the answer to: Catalan numbers: ways to balance 3 pairs of brackets?
There are C₃ = 5 ways to match 3 pairs of brackets; in general C_n = (1/(n+1))·C(2n, n).
What is the key idea?
A correct bracketing is a path that never goes below zero; Catalan numbers count those paths.
Is there a hint?
List them: ((())), (()()), (())(), ()(()), ()()(). Then check the formula.