Parenthesization/Examples/4

From ProofWiki
Jump to navigation Jump to search

Example of Parenthesization

A word of $4$ elements can be parenthesized in $5$ distinct ways:

$\quad a_1 \paren {a_2 \paren {a_3 a_4} }$
$\quad a_1 \paren {\paren {a_2 a_3} a_4}$
$\quad \paren {a_1 a_2} \paren {a_3 a_4}$
$\quad \paren {a_1 \paren {a_2 a_3} } a_4$
$\quad \paren {\paren {a_1 a_2} a_3} a_4$


Proof

From Number of Distinct Parenthesizations on Word, the number of distinct parenthesizations of a word $w$ of $n$ elements is the Catalan number $C_{n - 1}$:

$C_{n - 1} = \dfrac 1 n \dbinom {2 \paren {n - 1} } {n - 1}$


For $n = 4$ we have:

\(\ds C_4\) \(=\) \(\ds \dfrac 1 4 \dbinom {2 \times 3} 3\)
\(\ds \) \(=\) \(\ds \dfrac 1 4 \times \dfrac {6!} {3! \times 3!}\) Definition of Binomial Coefficient
\(\ds \) \(=\) \(\ds \dfrac 1 4 \times \dfrac {6 \times 5 \times 4} {3 \times 2 \times 1}\) Definition of Factorial
\(\ds \) \(=\) \(\ds 5\)

$\blacksquare$


Sources