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=22
  • There is 1 value for n=3:
    • 16=(22)2=2(22)
  • There are 2 values for n=4:
    • 256=((22)2)2=(2(22))2=(22)(22)
    • 65536=2((22)2)=2(2(22))

Any idea how to formulate a general solution?

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



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 nth Catalan number. However that is not to say that is your answer, because in the case of the number 2 you have the identity 24=42 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

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).

Source : Link , Question Author : barak manos , Answer Author : samerivertwice

Leave a Comment