Theorem: Number of Distinct Parenthesizations on Word

Let $w_n$ denote an arbitrary word of $n$ elements.
The number of distinct parenthesizations of $w_n$ is the Catalan number $C_{n - 1}$:
:$C_{n - 1} = \dfrac 1 n \dbinom {2 \paren {n - 1} } {n - 1}$

Proof:
Let $w_n$ denote an arbitrary word of $n$ elements.
Let $a_n$ denote the number of ways $W_n$ elements may be parenthesized.
First note that we have:
{{begin-eqn}}
{{eqn | l = a_1
      | r = 1
      | c = 
}}
{{eqn | l = a_2
      | r = 1
      | c = 
}}
{{eqn | l = a_3
      | r = 2
      | c = that is, $b_1 \paren {b_2 b_3}$ and $\paren {b_1 b_2} b_3$
}}
{{end-eqn}}
and from Parenthesization of Word of $4$ Elements:
:$a_4 = 5$
Consider a word $w_{n + 1}$ of $n + 1$ elements.
Then $w_{n + 1}$ can be formed as any one of:
:$w_1$ concatenated with $w_n$
:$w_2$ concatenated with $w_{n - 1}$
:$\dotsc$ and so on until:
:$w_n$ concatenated with $w_1$
Thus the $i$th row in the above sequence is the number of parenthesizations of $w_{n + 1}$ in which the two outermost parenthesizations contain $i$ and $n - i + 1$ terms respectively.
We have that:
:there are $a_i$ parenthesizations of $w_i$
:there are $a_{n - i + 1}$ parenthesizations of $w_{n - i + 1}$
Hence the total number of parenthesizations of $w_{n + 1}$ is the sum of all these parenthesizations for $1 \le i \le n$.
That is:
:$(1): \quad a_{n + 1} = a_1 a_n + a_2 a_{n - 1} + \dotsb + a_n a_1$
Let us start with the generating function:
:$\ds \map {G_A} z = \sum_{n \mathop = 1}^\infty a_n z^n$
Then:
{{begin-eqn}}
{{eqn | l = \map {G_A} z
      | r = z + \sum_{n \mathop = 2}^\infty \paren {a_1 a_n + a_2 a_{n - 1} + \dotsb + a_n a_1} z^n
      | c = from $(1)$
}}
{{eqn | r = z + \sum_{n \mathop = 1}^\infty a_n z^n \sum_{n \mathop = 1}^\infty a_n z^n
      | c = 
}}
{{eqn | r = z + \paren {\map {G_A} z}^2
      | c = 
}}
{{end-eqn}}
Thus $\map {G_A} z$ satisfies the quadratic equation:
:$\paren {\map {G_A} z}^2 - \map {G_A} z + z = 0$
By the Quadratic Formula, this gives:
:$\map {G_A} z = \dfrac {1 \pm \sqrt {1 - 4 z} } 2$
Since $\map {G_A} 0 = 0$, we can eliminate the positive square root and arrive at:
:$(2): \quad \map {G_A} z = \dfrac 1 2 - \dfrac {\sqrt {1 - 4 z} } 2$
Expanding $\sqrt {1 - 4 z}$ using the Binomial Theorem:
:$\ds \map {G_A} z = \dfrac 1 2 - \dfrac 1 2 \sum_{n \mathop = 0}^\infty \paren {-1}^n \dbinom {\frac 1 2} n 4^n z^n$
where:
:$\dbinom {\frac 1 2} 0 = 1$
and:
:$\dbinom {\frac 1 2} n = \dfrac {\frac 1 2 \paren {\frac 1 2 - 1} \dotsm \paren {\frac 1 2 - n + 1} } {n!}$
As a result:
:$\ds (3): \quad \map {G_A} z = -\dfrac 1 2 \sum_{n \mathop = 1}^\infty \paren {-1}^n \dbinom {\frac 1 2} n 4^n z^n$
We can expand $(3)$ as a Taylor series about $0$.
As such a series, when it exists, is unique, the coefficients must be $a_n$.
Hence:
{{begin-eqn}}
{{eqn | l = a_n
      | r = -\dfrac 1 2 \paren {-1}^n \dbinom {\frac 1 2} n 4^n
      | c = 
}}
{{eqn | r = \paren {-1}^{n - 1} \dfrac 1 2 \dfrac {\frac 1 2 \paren {\frac 1 2 - 1} \dotsm \paren {\frac 1 2 - n + 1} } {n!} 4^n
      | c = 
}}
{{eqn | r = \paren {-1}^n \dfrac 1 2 \dfrac {\paren {-1} \paren {1 - 2} \dotsm \paren {1 - 2 \paren {n - 1 } } 2^n} {n!}
      | c = 
}}
{{eqn | r = \dfrac 1 2 \dfrac {1 \times 3 \times \dotsb \times \paren {2 n - 3} 2^n} {n!}
      | c = 
}}
{{eqn | r = \dfrac 1 2 \dfrac {1 \times 3 \times \dotsb \times \paren {2 n - 3} n! 2^n} {n! n!}
      | c = multiplying top and bottom by $n!$
}}
{{eqn | r = \dfrac 1 2 \dfrac {1 \times 2 \times 3 \times 4 \times \dotsb \times \paren {2 n - 4} \paren {2 n - 3} \paren {2 n - 2} \paren {2 n} } {\paren {n!}^2}
      | c = 
}}
{{eqn | r = \dfrac 1 2 \dfrac {1 \times 2 \times 3 \times 4 \times \dotsb \times \paren {2 n - 2} } {\paren {\paren {n - 1}!}^2}
      | c = 
}}
{{eqn | r = \frac 1 n \binom {2 n - 2} {n - 1}
      | c = 
}}
{{end-eqn}}
{{qed}}