## FANDOM

10,835 Pages

Consider a power tower of $$\omega$$s of size $$n$$. How many different values can we get by putting parentheses in the tower?

Call the result $$W(n)$$. It's obvious that $$W(1) = W(2) = 1$$. $$W(3) = 2$$ because we have $$(\omega^\omega)^\omega$$ and $$\omega^{(\omega^\omega)}$$. We can see that $$W(4) = 5$$ through the following configurations:

$\omega^{\omega^{}\omega^{}\omega^{}},\,\omega^{\omega^{\omega^{\omega^{}}}},\,\omega^{\omega^{\omega^{}\omega^{}}},\,\omega^{\omega^{}\omega^{\omega^{}}},\,\omega^{\omega^{\omega^{}}\omega^{}}$

For $$W(5)$$, we have $$14$$ configurations:

$(\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})}),\,(\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})$

However, two of these numbers are equal, $$\omega^{\omega(\omega^{(\omega^{\omega})})}$$ and $$\omega^{(\omega^{\omega(\omega^{\omega})})}$$. (They are both $$\omega^{\omega^{\omega^\omega}}$$.) So $$W(5)$$ is actually $$13$$.

The first few values of $$W(n)$$ are 1, 1, 2, 5, 13, 32, 79, 193, 478, 1196, 3037, 7802, 20287, 53259, 141069, 376449, 1011295, 2732453, 7421128, 20247355, ... (OEIS).

If we ignore duplicates, we get the famous Catalan numbers $$C_n$$: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, ... (OEIS). Their formula is $$C_n = \frac{1}{2n + 1}{2n\choose n}$$, which is an upper bound for $$W(n)$$.

The unsolved problem: find a formula for $$W(n)$$.

### Update 1

I will offer an upper bound for $$W(n)$$ based on a special case of the omegatowers. It introduces a way of finding redundant terms, essentially providing a lower bound for $$C_n - W(n)$$.

Consider cases like $$\omega^{\omega^{\omega\omega\omega^{\omega^{\omega\omega^{\omega}}}}}$$, which are power towers of omegas with extra omegas inserted before other omegas except at the top and bottom layers. We can encode these special omegatowers as a binary string. Each omega that ends a layer is a 1, and all others are 0s. The example I gave you is encoded as 110011011. Note that such a string always starts with 1 and ends with 11.

Note that the multiplied omegas get "absorbed" into the expression. So when evaluated, 110011011 just becomes 111111. If two strings A and B encode equal expressions, I'll write A = B.

A string of length $$n$$ represents a valid omegatower of $$n$$ terms. Consider a case where we just have one 0. With 8 terms, we can write 10111111 = 11011111 = 11101111 = 11110111 = 11111011 for 5 redundant towers. In general there are $$n - 3$$ redundant towers, so we lose $$n - 4$$ omegatowers. This essentially proves that $$W(n) \leq C_(n) - (n - 4)$$ for $$n \geq 5$$.

But that's not all. What about more zeroes? We take a string of 1's and convert $$k$$ of them to zeroes. There are $${n - 3 \choose k}$$ ways to do this, so we lose $${n - 3 \choose k} - 1$$ omegatowers for each value of $$k$$. In total, the loss is

$\sum_{k = 0}^{n - 4}\left[{n - 3 \choose k} - 1\right] = \sum_{k = 0}^{n - 4} {n - 3 \choose k} - (n - 3) = \sum_{k = 0}^{n - 3} {n - 3 \choose k} - {n - 3 \choose n - 3} - (n - 3) = 2^{n - 3} - n + 2\text{ or something.}$

So the upper bound is

$W(n) \leq C_n - 2^{n - 3} + n - 2 \text{ for } n \geq 5.$