In the expression $3^{3^{3}}$, the order of operations can be indicated in two ways: $\left(3^{3}\right)^{3}=3^{9}$ and $3^{\left(3^{3}\right)}=3^{27}$, where the results are different. In how many ways can we parenthesize the (1) expression, and how many different results can we obtain?

![](https://cdn.mathpix.com/cropped/2024_05_02_c6511492b1eba6b8c3f3g-1.jpg?height=173&width=249&top_left_y=266&top_left_x=927)
a) In the expression (1), 5 threes appear, and we denote the number of different parenthesizations by $z_{5}$; generally, if $i$ threes appear, then the number of different parenthesizations is denoted by $z_{i}$. We know that

$$
z_{2}=1, \quad z_{3}=2,
$$

and our task is to determine $z_{5}$. Parenthesization means that in the expression (1), we select a base and an exponent, and then we separately parenthesize the base and the exponent. The base can contain 1, 2, 3, or 4 threes, in which case the exponent will contain 4, 3, 2, or 1 threes, respectively. The number of parenthesizations in each case is obtained by multiplying the possible parenthesizations of the corresponding base-exponent pairs, and then summing the products:

$$
z_{5}=1 \cdot z_{4}+z_{2} \cdot z_{3}+z_{3} \cdot z_{2}+z_{4} \cdot 1
$$

Based on this, we first need to determine $z_{4}$. In the case of four threes, our task is easier, as the "base" can now only contain 1, 2, or 3 threes, so the number of parenthesizations is:

$$
z_{4}=1 \cdot z_{3}+z_{2} \cdot z_{2}+z_{3} \cdot 1
$$

The value of this, according to (2), is 5, so according to (3), the value of $z_{5}$ is 14, meaning that the expression (1) can be parenthesized in 14 different ways.

b) Writing down the 14 possible parenthesizations, using the relationship $\left(a^{b}\right)^{c}=a^{b c}$, each can be brought to the form $3^{3^{x}}$, and the values of $x$ that occur are $4,5,6,10,27,28,81,3^{9}$, and $3^{27}$. Thus, the 14 different parenthesizations provide at most 9 different values, but we do get this many, since the 9 numbers listed here are all different. (This can be shown, for example, by using the fact that powers with the same base greater than one are only equal if the exponents are equal.)

Note. Using the line of thought in part $a$), we get that

$$
z_{n}=1 \cdot z_{n-1}+z_{2} \cdot z_{n-2}+\ldots+z_{n-2} \cdot z_{2}+z_{n-1} \cdot 1
$$

from which, after a little calculation, we get that

$$
z_{n}=\frac{1}{n}\binom{2 n-2}{n-1}
$$