Parenthesization/Examples/4
< Parenthesization/Examples(Redirected from Parenthesization of Word of 4 Elements)
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
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {3-4}$ Generating Functions
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $42$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $42$