Definition:Parenthesization
Jump to navigation
Jump to search
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$