Parenthesization/Examples/2
Jump to navigation
Jump to search
Example of Parenthesization
A word of $2$ elements can be parenthesized in only $1$ distinct way:
- $\quad \paren {a_1 a_2}$
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 = 2$ we have:
\(\ds C_1\) | \(=\) | \(\ds \dfrac 1 {1 + 1} \dbinom {2 \times 1} 1\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac 1 2 \times 2\) | Binomial Coefficient with One | |||||||||||
\(\ds \) | \(=\) | \(\ds 1\) |
$\blacksquare$
Sources
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $42$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $42$