# How many values of 222…22^{2^{2^{.^{.^{.^{2}}}}}} depending on parenthesis?

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

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

The number of Dyck words of length $$2n2n$$ (i.e. representing $$2n2n$$ sets of nested brackets, is given by the $$nn$$th Catalan number. However that is not to say that is your answer, because in the case of the number $$22$$ you have the identity $$24=422^4=4^2$$ to contend with, so you need to eliminate those identical solutions from your answer.
Based on $$nn$$ up to $$1111$$, the solutions to this give $$1,1,1,2,3,3,4,6,8,10,13,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 $$(n2)2=n(22)(n^2)^2=n^{(2^2)}$$.