Let $\alpha\in\mathbf{Ord}$ and $n\in\mathbb{N}^+$.


Let $F\_\alpha(n)$ be the number of distinct values taken by ordinal exponentiation $\underbrace{\alpha \hat{\phantom{\hat{}}} \alpha \hat{\phantom{\hat{}}} \dots \hat{\phantom{\hat{}}} \alpha}\_\text{n times}$ with parentheses inserted in all possible ways. 


The case $\alpha<\omega$ (i.e. natural numbers) was studied in "The Nesting and Roosting Habits of The Laddered Parenthesis", by R. K. Guy and J. L. Selfridge. Here I am interested in a case when $\alpha\ge\omega$.


*Questions*: Does the sequence $F\_\alpha(n)$ depend on $\alpha$ in this case? Is there a simple closed form formula, recurrence relation or generating function for this sequence? What can be said about its asymptotic growth? What is $\lim\limits\_{n\to\infty}\frac{F\_\alpha(n+1)}{F\_\alpha(n)}$? Do odd and even numbers occur infinitely often in the sequence?


---


$F\_\omega(n)$ is given in [A199812](http://oeis.org/A199812): $1, 1, 2, 5, 13, 32, 79, 193, 478, 1196, 3037, 7802, 20287, 53259, 141069, 376449, 1011295, \dots$


It is bounded by [Catalan numbers](http://oeis.org/A000108) $\frac{(2n-2)!}{n! (n-1)!}$. The first difference occurs at $n=5$ because among $14$ possible parenthesizations there are only $13$ distinct ordinals:
$(((\omega^\omega)^\omega)^\omega)^\omega < ((\omega^\omega)^\omega)^{\omega^\omega} < ((\omega^\omega)^{\omega^\omega})^\omega < ((\omega^{\omega^\omega})^\omega)^\omega < (\omega^{\omega^\omega})^{\omega^\omega} < (\omega^\omega)^{(\omega^\omega)^\omega} < $
$(\omega^{(\omega^\omega)^\omega})^\omega < \omega^{((\omega^\omega)^\omega)^\omega} < \pmb{(\omega^\omega)^{\omega^{\omega^\omega}} = \omega^{(\omega^\omega)^{\omega^\omega}}} < (\omega^{\omega^{\omega^\omega}})^\omega < \omega^{(\omega^{\omega^\omega})^\omega} < \omega^{\omega^{(\omega^\omega)^\omega}} < \omega^{\omega^{\omega^{\omega^\omega}}}$



Number of distinct values taken by $\alpha$ ^ $\alpha$ ^ $\dots$ ^ $\alpha$ with parentheses inserted in all possible ways, $\alpha\in\mathbf{Ord}$
The sequence $F\_{\alpha}(n)$ indeed does not depend on $\alpha$ when $\alpha \geq \omega$. This question is closely related to [this other question](https://mathoverflow.net/questions/103486), and I will refer to my answer in that question.


Let $S\_\alpha(n)$ be the set of ordinals defined by $\alpha ^ {\alpha ^ {\cdots ^ \alpha}}$ with all possible arrangements of parentheses. Since $\alpha = \alpha^{\alpha^0}$ and $(\alpha^{\alpha ^ \beta})^{\alpha^{\alpha^\gamma}} = \alpha^{\alpha ^ {\beta + \alpha^\gamma}}$, every element of $S\_\alpha(n)$ is of the form $\alpha^{\alpha ^ \beta}$. So we define $T\_\alpha (n) = \lbrace \beta | \alpha^{\alpha^\beta} \in S\_\alpha(n) \rbrace$. We observe that $T\_\alpha(0) = \lbrace 0 \rbrace$ and $T\_\alpha(n) = \lbrace \beta + \alpha^\gamma | \beta \in T\_\alpha(i), \gamma \in T\_\alpha(j), i + j = n - 1 \rbrace$.


From my answer to the other question, we observe that $T\_\alpha(n)$ is contained in the set $E(\alpha)$, which I refer to as the "exponential polynomials over the base $\alpha$". For each element $\beta$ of $E(\alpha)$, we can write $\beta$ in the iterative normal form to the base $\alpha$, which I describe as follows:


0 is represented as 0


$\beta$ is represented as $\alpha^{\beta\_1} + \alpha^{\beta\_2} + \ldots + \alpha^{\beta\_n}$, where $\beta\_1 \geq \beta\_2 \geq \ldots \geq \beta\_n$ and each $\beta\_i$ is itself represented in iterative normal form.


We claim that, for any n and any $\alpha, \beta \geq \omega$, $T\_\alpha(n)$, when written in iterative normal form, is the same set as $T\_\beta(n)$, except the base $\beta$ is replaced everywhere it appears by $\alpha$. If we let $f(\gamma)$ be the ordinal obtained by replacing the base $\beta$ by $\alpha$ everywhere in the iterative normal form of $\gamma$, our claim amounts to $T\_{\alpha}(n) = f(T\_\beta(n))$. From our above expression for $T\_\alpha(n)$, we see that it suffices to show that $f(\gamma + \beta^\delta) = f(\gamma) + \alpha^{f(\delta)}$ for any $\gamma, \delta \in E(\beta)$.


Let $\gamma = \beta^{\gamma\_1} + \beta^{\gamma\_2} + \ldots + \beta^{\gamma\_n}$. Let $m$ be the largest index such that $\gamma\_m \geq \delta$. Then we claim that


$\gamma + \beta^\delta = \beta^{\gamma\_1} + \beta^{\gamma\_2} + \ldots + \beta^{\gamma\_m} + \beta^\delta$


(note that this is in iterative normal form, provided that $\gamma\_i$ and $\delta$ are.)


First we prove:


Lemma. If $\beta, \mu, \nu$ are any ordinals such that $\mu < \nu$, then $\beta^\mu + \beta^\nu = \beta^\nu$.


Proof: Let $\beta = \omega^{\beta\_1} + \omega^{\beta\_2} + \ldots + \omega^{\beta\_n}$ be the Cantor Normal Form for $\beta$. Then the leading term of the Cantor Normal Form of $\beta^\mu$ will be $\omega^{\beta\_1 \mu}$, i.e.


$\beta^\mu = \omega^{\xi\_1} + \omega^{\xi\_2} + \ldots + \omega^{\xi\_m}$ where $\xi\_i \leq \beta\_1 \mu$.


Since $\omega$ is a principal ordinal, for $\mu < \nu, \omega^\mu + \omega^\nu = \omega^\nu$. Therefore


$\beta^\mu + \beta^\nu = \omega^{\xi\_1} + \omega^{\xi\_2} + \ldots + \omega^{\xi\_m} + \beta^\nu = \beta^\nu$, as desired. (end of proof of Lemma)


Therefore, since $\gamma\_i \leq \delta$ for $m+1 \leq i \leq n$, we have


$\beta^{\gamma\_{m+1}} + \ldots + \beta^{\gamma\_n} + \beta^\delta = \beta^\delta$


and therefore


$\gamma + \beta^\delta = \beta^{\gamma\_1} + \beta^{\gamma\_2} + \ldots + \beta^{\gamma\_m} + \beta^\delta$.


We have


$f(\gamma) = \alpha^{f(\gamma\_1)} + \alpha^{f(\gamma\_2)} + \ldots + \alpha^{f(\gamma\_n)}$


$f(\gamma + \beta^\delta) = \alpha^{f(\gamma\_1)} + \alpha^{f(\gamma\_2)} + \ldots + \alpha^{f(\gamma\_m)} + \alpha^{f(\delta)}$,


and, provided that $m$ is the largest index such that $f(\gamma\_m) \geq f(\delta)$, the same argument as above shows that


$f(\gamma) + \alpha^{f(\delta)} = \alpha^{f(\gamma\_1)} + \alpha^{f(\gamma\_2)} + \ldots + \alpha^{f(\gamma\_n)} + \alpha^{f(\delta)} $ $= \alpha^{f(\gamma\_1)} + \alpha^{f(\gamma\_2)} + \ldots + \alpha^{f(\gamma\_m)} + \alpha^{f(\delta)} = f(\gamma + \beta^\delta)$.


So we are done if we can show that for all $\gamma, \delta \in E(\beta)$, $\gamma < \delta \Leftrightarrow f(\gamma) < f(\delta)$.


This follows from the fact that we can describe the comparison relation < using the same inductive rules, regardless of base. The inductive rules are as follows:


0 is less than any ordinal besides 0.


If $\gamma = \beta^{\gamma\_1} + \beta^{\gamma\_2} + \ldots + \beta^{\gamma\_m}$, and $\delta = \beta^{\delta\_1} + \beta^{\delta\_2} + \ldots + \beta^{\delta\_n}$, with the $\gamma\_i$ and the $\delta\_i$ weakly decreasing, than $\gamma < \delta$ if and only if one of the following two conditions hold:


1. For some $i$, $\gamma\_i < \delta\_i$ and for all $1 \leq j < i, \gamma\_j = \delta\_j$.
2. $m < n$ and for all $1 \leq i \leq m$, $\gamma\_i = \delta\_i$.


It is easy to see that if the second condition holds, then $\gamma < \delta$. So assume the first condition holds. Since $\beta \geq \omega$ and $\delta\_i \geq \gamma\_i + 1$,


$\beta^{\delta\_i} \geq \beta^{\gamma\_i + 1} \geq \beta^{\gamma\_i} \omega > \beta^{\gamma\_i} m \geq \beta^{\gamma\_i} + \beta^{\gamma\_{i+1}} + \ldots + \beta^{\gamma\_m}$, so


$\beta^{\delta\_1} + \beta^{\delta\_2} + \ldots + \beta^{\delta\_n} \geq \beta{\delta\_1} + \beta^{\delta\_2} + \ldots + \beta^{\delta\_i} = \beta^{\gamma\_1} + \beta^{\gamma\_2} + \ldots + \beta^{\gamma\_{i-1}} + \beta^{\delta\_i} > \beta^{\gamma\_1} + \beta^{\gamma\_2} + \ldots + \beta^{\gamma\_{m}}$.


Going the other way, observe that, if neither conditions 1 nor 2 hold for $\gamma < \delta$, nor conditions 1 nor 2 hold for $\delta < \gamma$, we must have $m = n$ and $\gamma\_i = \delta\_i$ for $1 \leq i \leq m$, so $\gamma = \delta$. So if $\gamma < \delta$, either conditions 1 or 2 must hold.


We have shown that $T\_\alpha(n)$ and $T\_\beta(n)$ are the same ordinals except for a change of base from $\alpha$ to $\beta$. It follows that $S\_\alpha(n)$ and $S\_\beta(n)$ are the same except for the same change of base. So $F\_\alpha(n) = F\_\beta(n)$ for any $\alpha, \beta \geq \omega$.




---


As for the asymptotics of $F\_\omega(n)$, all I can prove is that $F\_\omega(n) \geq 2^{n-2}$. Take any binary string of n-2 symbols. Starting from $\omega^\omega$, apply the function $\alpha \rightarrow \alpha^\omega$ if the $i$th symbol is a 0, and apply the function $\alpha \rightarrow \omega^\alpha$ if the $i$th symbol is a 1. Defining $\beta$ by $\alpha = \omega^{\omega^\beta}$, the two operations affect $\beta$ by $\beta \rightarrow \beta + 1$ and $\beta \rightarrow \omega^\beta$ respectively. It's not hard to see that two distinct binary strings lead to two different final ordinals.


I conjecture that $\lim\_{n \rightarrow \infty} \frac{F\_\omega(n+1)}{F\_\omega(n)} = 4$, but am nowhere close to a proof.


