2022-06 A way of putting parentheses


We have an expression \(x_0 \div x_1 \div x_2 \div \dots \div x_n\). A way of putting \(n-1\) left parentheses and \(n-1\) right parenthese is called ‘parenthesization’ if it is valid and completely clarify the order of operations. For example, when \(n=3\), we have the following five parenthesizations.
\[ ((x_0\div x_1)\div x_2)\div x_3, \enspace (x_0\div (x_1\div x_2))\div x_3, \enspace (x_0\div x_1)\div (x_2\div x_3),\]
\[x_0\div ((x_1\div x_2)\div x_3), \enspace x_0\div (x_1\div (x_2\div x_3)).
\]


(a) For an integer \(n\), how many parenthesizations are there?
(b) For each parenthesization, we can compute the expression to obtain a fraction with some variables in the numerator and some variable in the denominator. For an integer \(n\), determine which fraction occur most often. How many times does it occur?

GD Star Rating
loading...