Let's take the expression $$\LARGE \underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}_n$$

and put a nonnegative number of parentheses around them in a logically coherent way. How many possible different evaluations are there?

To clarify what I mean, I'll take some examples.

When $n = 1$, the expression $2$ is, duh, $2$. It can only be evaluated one way.

When $n = 2$, $2^2 = 4$, and that's the only way it can be evaluated.

When $n = 3$, we can evaluate $\displaystyle 2^{2^2}$ to get $2^4 = 16$ or evaluate $\displaystyle \left(2^2\right)^2$ to get $4^2 = 16$. Coincidentally, these two values are the same, and there is only one unique answer.

When $n = 4$, we have the following possibilities:

  • $\displaystyle 2^{2^{2^2}} = 2^{2^4} = 2^{16}$
  • $\displaystyle 2^{(2^2)^2} = 2^{4^2} = 2^{16}$
  • $\displaystyle \left(2^{2^2}\right)^2 = \left(2^4\right)^2 = 2^8$
  • $\displaystyle \left(2^2\right)^{2^2} = 4^4 = 2^8$

These $4$ results yield $2$ different values, thus the answer is $2$.

Is there a general formula for finding the number of solutions for any $n \in \mathbb{N}$? I feel like this question involves combinatorics but I can't exactly see where and how to start. Feel free to edit the LaTeX and tags as necessary.

  • 1
    $\begingroup$ @PedroTamaroff - would you mind explaining further? I get that stars and bars (I learned them as balls and urns, but the concept seems to be the same) is the way to find expressions written differently, but that alone doesn't necessarily determine whether the two expressions evaluate to two different values. $\displaystyle \left(2^{2^2}\right)^2$ and $\displaystyle \left(2^2\right)^{2^2}$, for example, are written differently but yield the same value. $\endgroup$ – 2012ssohn Mar 17 '14 at 21:16
  • $\begingroup$ I rushed it. However, consider a string of $n$ twos $\underbrace{2\cdots 2}_n$. It might help to think it in the small case. For $n=4$, we have $$\eqalign{ & \left( {a \times a} \right) \times \left( {a \times a} \right) \to {\left( {{a^a}} \right)^{\left( {{a^a}} \right)}} \cr & a \times \left( {a \times \left( {a \times a} \right)} \right) \to {a^{\left( {{a^{\left( {{a^a}} \right)}}} \right)}} \cr} $$ and so on. Think about in how many ways you can insert parentheses. $\endgroup$ – Pedro Tamaroff Mar 17 '14 at 21:31
  • 2
    $\begingroup$ See the following paper: Fvrits Göbel and Rob P. Nederpelt, The number of numerical outcomes of iterated powers American Mathematical Monthly 78 #10 (December 1971), 1097-1103. $\endgroup$ – Dave L. Renfro Mar 18 '14 at 15:24

I would just comment, but I don't have any reputation yet, so this doesn't represent an answer but rather my initial thoughts.

Together with "stars and bars," it seems like the solution will involve some kind of recursive analysis (so that we can ignore nested parentheses). Define $S(n)$ as the number of different evaluations of $$\LARGE \underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}_n,$$ and define $n$ as the number of "terms" of this expression (for convenience).

Say you already know $S(1), S(2), \ldots, S(n)$ and wish to solve for $S(n+1)$. Now, we know that with $$\LARGE \underbrace{2^{2^{2^{\cdot^{\cdot^{\cdot^{2}}}}}}}_{n+1},$$ there are two different ways in which we can place (unnested) parentheses around the $2$'s to separate the expression into one expression with $n$ terms and one expression with $1$ term (either group the first $n$ or last $n$ terms). In each of these cases, there will be $S(n)$ different ways to evaluate the expression with $n$ terms, and $S(1) = 1$ different ways to evaluate the expression with 1 term. Going on, there are three different ways to separate the expression into an expression with $n-1$ terms and either two expressions with $1$ term (if we leave $1$ term on either side of the $n-1$ grouped terms) or one expression with $2$ terms (if the $n-1$ grouped terms are either the first or last $n-1$ terms). We can keep doing this for $n+1-k$ for each $k \leq n$, each time looking at the $k+1$ possible places where the $n-k+1$ grouped terms can occur; however, notice that we will start to repeat once $n-k+1 < (n+1)/2$.

Of course, because of the issue you mentioned, in each of these individual cases, finding the number of unique evaluations won't be as simple as something like $S(n-4)\cdot S(3)\cdot S(2)$ because there are repeats. I suspect that this might be unique to $2$, i.e. might be because $2^2 = 2\cdot 2$ so that, e.g., $2^{2^2} = 2^{2\cdot 2} = (2^2)^2$. So, it might be easier to first work out this problem with a number other than $2$; maybe, for example, things will work out better with $3$.

This all makes sense in my head--I hope I communicated it well enough that at least someone gets what I'm trying to say.

EDIT: it might suffice to look only at the possible ways in which the $2$'s can be grouped (by placing parentheses) into "left" and "right," and then examining the number of unique evaluations of both the left and right groupings. Ideally, you'd eventually end up with, for each left-right grouping, the total number of unique evaluations given that grouping, and then you could sum over all ($n-1$) possible left-right groupings (in the case of $n$ terms). Does this make any sense?

  • $\begingroup$ What you describe is essentially the recurrence leading to Catalan numbers $\endgroup$ – vonbrand Apr 6 '14 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.