WordGPT

Catalan numbers: ways to balance 3 pairs of brackets

Exercise · Level 3 (Medium)

In how many ways can 3 pairs of brackets be written so that they are correctly matched?

Cn=1n+1(2nn)C_n=\frac1{n+1}\binom{2n}{n}

wordgptpro.com

Solution

  1. The correct arrangements for 3 pairs are

    ((())), (()()), (())(), ()(()), ()()()((())),\ (()()),\ (())(),\ ()(()),\ ()()()
    (1)
  2. That is five. The formula for nn pairs is the Catalan number, Cn=1n+1(2nn)C_n=\tfrac{1}{n+1}\binom{2n}{n}:

    C3=14(63)=204=5\begin{aligned}C_3&=\frac14\binom63\\&=\frac{20}{4}=5\end{aligned}
    (2)
  3. 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.

Answer55

wordgptpro.com

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

  1. The correct arrangements for 3 pairs are

    ((())), (()()), (())(), ()(()), ()()()((())),\ (()()),\ (())(),\ ()(()),\ ()()()
    (1)
  2. That is five. The formula for nn pairs is the Catalan number, Cn=1n+1(2nn)C_n=\tfrac{1}{n+1}\binom{2n}{n}:

    C3=14(63)=204=5\begin{aligned}C_3&=\frac14\binom63\\&=\frac{20}{4}=5\end{aligned}
    (2)
  3. 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.

Related problems

More probability and puzzles

    Catalan numbers: ways to balance 3 pairs of brackets: answer and solution | WordGPT