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.


  • 8
    $\begingroup$ 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. $\endgroup$ – Yiannis Galidakis Nov 24 '16 at 12:27
  • 4
    $\begingroup$ 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)}$. $\endgroup$ – MJD Nov 28 '16 at 0:05
  • 3
    $\begingroup$ Are you sure that's not $8$ values for $n = 6$? Sloane's could be wrong, though. oeis.org/A002845 $\endgroup$ – Mr. Brooks Nov 28 '16 at 22:08
  • 6
    $\begingroup$ Aha, OEIS gives a reference to “The Nesting and Roosting Habits of the Laddered Parenthesis by Guy and Selfridge. $\endgroup$ – MJD Nov 30 '16 at 15:14
  • 1
    $\begingroup$ Maybe the question should be asked at mathoverflow.net $\endgroup$ – Ernesto Iglesias Feb 8 '17 at 20:59

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

| cite | improve this answer | |
  • 1
    $\begingroup$ 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. $\endgroup$ – r.e.s. Apr 28 '17 at 14:12
  • $\begingroup$ @r.e.s. Thanks. I wasn't sure how studied a subject it was, although I knew I had seen arrows. I've standardised what I put; pls let me know if wrong. $\endgroup$ – samerivertwice Apr 28 '17 at 15:04

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.