How many values of $2^{2^{2^{.^{.^{.^{2}}}}}}$ depending on parenthesis?

Suppose we have a power tower consisting of $2$ occurring $n$ times:

$$\huge2^{2^{2^{.^{.^{.^{2}}}}}}$$

How many values can we generate by placing any number of parenthesis?

It is fairly simple for the first few values of $n$:

• There is $1$ value for $n=1$:
  • $2=2$
• There is $1$ value for $n=2$:
  • $4=2^{2}$
• There is $1$ value for $n=3$:
  • $16=({2^{2})^{2}}=2^{(2^{2})}$
• There are $2$ values for $n=4$:
  • $256=(({2^{2})^{2}})^2=(2^{(2^{2})})^2=(2^{2})^{(2^{2})}$
  • $65536=2^{(({2^{2})^{2}})}=2^{(2^{(2^{2})})}$

Any idea how to formulate a general solution?

I'm thinking that it might be feasible using a recurrence relation.

Thanks

Solution 1:

There's a maths of this symmetry, they're called Dyck Words, which John Baez talks about here with some helpful diagrams. It is the maths which governs the number of ways in which a certain number of sets of brackets can be nested. It is the symmetries of these Dyck words which give rise to the number of different solutions to any given tetration.

The number of Dyck words of length $2n$ (i.e. representing $2n$ sets of nested brackets, is given by the $n$th Catalan number. However that is not to say that is your answer, because in the case of the number $2$ you have the identity $2^4=4^2$ to contend with, so you need to eliminate those identical solutions from your answer.

I conjectured a solution to this with this question here:

Based on $n$ up to $11$, the solutions to this give $1, 1, 1, 2, 3, 3, 4, 6, 8, 10, 13,$ which match https://oeis.org/A017818.

But I later formed the opinion that I missed the mark with that, as it fails to consider permutations of further dyck words either side of any $(n^2)^2=n^{(2^2)}$.