Definition:Parenthesization

Definition

Let $\circ$ be a product defined on a set $S$.

Let $a_1 \circ a_2 \circ \cdots a_i \circ \cdots \circ a_n$ denote a word in $S$ for some $n > 2$.

To distinguish all possible products of $a_1, a_2, \dotsc, a_n$, parentheses are inserted into the word.

A set of parentheses applied on a product is called a parenthesization of that word.

Equivalent Parenthesizations

Two parenthesizations of $a_1, \ldots, a_n$ are equivalent if and only if the product defined by them yields the same result.

Examples

Parenthesization of Word of $2$ Elements

A word of $2$ elements can be parenthesized in only $1$ distinct way:

$\quad \paren {a_1 a_2}$

Parenthesization of Word of $3$ Elements

A word of $3$ elements can be parenthesized in $2$ distinct ways:

$\quad a_1 \left({a_2 a_3}\right)$

$\quad \left({a_1 a_2}\right) a_3$

Parenthesization of Word of $4$ Elements

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$