Number of distinct values taken by $\alpha$ ^ $\alpha$ ^ $\dots$ ^ $\alpha$ with parentheses inserted in all possible ways, $\alpha\in\mathbf{Ord}$ 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: $1, 1, 2, 5, 13, 32, 79, 193, 478, 1196, 3037, 7802, 20287, 53259, 141069, 376449, 1011295, \dots$

It is bounded by Catalan numbers $\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}}}$
 A: The sequence $F_{\alpha}(n)$ indeed does not depend on $\alpha$ when $\alpha \geq \omega$. This question is closely related to this other question, 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:


*

*For some $i$, $\gamma_i < \delta_i$ and for all $1 \leq j < i, \gamma_j = \delta_j$.

*$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.
