(x^x)^(x^x), x^(x^(x^x)), etc...

[Edwin Clark]

On Tue, 29 Apr 2003, N. J. A. Sloane wrote:

> Isn't that the subject of the following well-known article?
> 
> %D A003018 R. K. Guy and J. L. Selfridge, The nesting and roosting 
habits of the laddered parenthesis. Amer. Math. Monthly 80 (1973), 868-876.
> 
> (there are numerous references to it in the OEIS)
> 

Yes, but none linked to A000081 (Rooted Trees).

The observation that the number of distinct functions obtained by
inserting parentheses in x^x^x^...^x where there are n x's is equal to the
number of rooted trees with n nodes apparently appeared first in an
earlier paper (referenced by Guy and Selfridge):

F. G\"{o}bel and R. P. Nederpelt,
The number of numerical outcomes of iterated powers,
Amer. Math. Monthly, 80 (1971), 1097-1103

May I suggest that these two references be added to the references for
A000081 (rooted trees) and that this interpretation of sequence A000081 be
added to the comments with a link to A003018.


--Edwin Clark