# 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

• It's a special case of the number of different words of inserting $n$ parentheses in $n+1$ (distinct) letters, hence an upper bound for your number is given by the Catalan numbers, but the intractability of this particular case lies in that we have to deal with a special case of the mutuabola $2^{(2^2)}=(2^2)^2$, hence you have to count out words which contain this particular grouping and give non-distinct values, thereby lowering the count. – Yiannis Galidakis Nov 24 '16 at 12:27
• It's not quite that simple, because, while that gives you $\left(\color{darkred}{{2^{(2^2)}}}\right)^2 = \left(\color{darkred}{{(2^2)}^2}\right)^2$, it does not also give you $\left({(2^2)}^2\right)^2= {(2^2)}^{(2^2)}$. – MJD Nov 28 '16 at 0:05
• Are you sure that's not $8$ values for $n = 6$? Sloane's could be wrong, though. oeis.org/A002845 – Mr. Brooks Nov 28 '16 at 22:08
• Aha, OEIS gives a reference to “The Nesting and Roosting Habits of the Laddered Parenthesis by Guy and Selfridge. – MJD Nov 30 '16 at 15:14
• Maybe the question should be asked at mathoverflow.net – Ernesto Iglesias Feb 8 '17 at 20:59

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.
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)}$$.
• For tetration there are more-or-less standard notations (e.g. Knuth-arrows $a\uparrow\uparrow b$), but $a\uparrow b$ is not one of them. – r.e.s. Apr 28 '17 at 14:12