A199812 Number of distinct values taken by w^w^...^w (with n w's and parentheses inserted in all possible ways) where w is the first transfinite ordinal omega.

1, 1, 2, 5, 13, 32, 79, 193, 478, 1196, 3037, 7802, 20287, 53259, 141069, 376449, 1011295, 2732453, 7421128, 20247355

Offset

1,3

Comments

Any transfinite ordinal can be used instead of omega, yielding the same sequence.

It appears that 2nd differences of this sequence give A174145 (starting from offset 2).

Conjectured extension of this sequence is given by A255170.

Links

Table of n, a(n) for n=1..20.

Libor Behounek, Ordinal Calculator

R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis

MathOverflow, A discussion related to this sequence

Eric Weisstein's World of Mathematics, Ordinal Number

Formula

Conjecture: a(n) ~ c * d^n * n^(-3/2), where c = 0.664861... and d = A051491 = 2.955765... - Vladimir Reshetnikov, Aug 11 2016

Example

For n=5 there are 14 possible parenthesizations, but only 13 of them produce distinct ordinals: (((w^w)^w)^w)^w < ((w^w)^w)^(w^w) < ((w^w)^(w^w))^w < ((w^(w^w))^w)^w < (w^(w^w))^(w^w) < (w^w)^((w^w)^w) < (w^((w^w)^w))^w < w^(((w^w)^w)^w) < (w^w)^(w^(w^w)) = w^((w^w)^(w^w)) < (w^(w^(w^w)))^w < w^((w^(w^w))^w) < w^(w^((w^w)^w)) < w^(w^(w^(w^w))). So, a(5)=13.

Mathematica

(* Slow exhaustive search *)
_ \[Precedes] {} = False;
{} \[Precedes] {__} = True;
{a_ \[Diamond] _, ___} \[Precedes] {b_ \[Diamond] _, ___} := a \[Precedes] b /; a =!= b;
{a_ \[Diamond] m_, ___} \[Precedes] {a_ \[Diamond] n_, ___} := m < n /; m != n;
{z_, x___} \[Precedes] {z_, y___} := {x} \[Precedes] {y};
m_ \[CirclePlus] {} := m;
{} \[CirclePlus] n_ := n;
{x___, a_ \[Diamond] m_} \[CirclePlus] {a_ \[Diamond] n_, y___} := {x, a \[Diamond] (m + n), y};
{x___, a_ \[Diamond] m_} \[CirclePlus] z : {b_ \[Diamond] n_, y___} := If[a \[Precedes] b, {x} \[CirclePlus] z, {x, a \[Diamond] m, b \[Diamond] n, y}];
{} \[CircleTimes] _ = {};
_ \[CircleTimes] {} = {};
{a_ \[Diamond] m_, x___} \[CircleTimes] {b_ \[Diamond] n_} := If[b === {}, {a \[Diamond] (m n), x}, {(a \[CirclePlus] b) \[Diamond] n}];
x_ \[CircleTimes] {y_, z__} := x \[CircleTimes] {y} \[CirclePlus] x \[CircleTimes] {z};
f[1] = {{{} \[Diamond] 1}};
f[n_] := f[n] = Union[Flatten[Table[Outer[#1 \[CircleTimes] {#2 \[Diamond] 1} &, f[k], f[n - k], 1], {k, n - 1}], 2]];
Table[Length[f[n]], {n, 1, 17}]

Crossrefs

Cf. A000108 (upper bound), A174145 (2nd differences?), A255170 (conjectured extension), A005348, A002845, A198683, A000081 (similar asymptotics), A051491.

Sequence in context: A098156 A267862 A098586 * A255170 A255630 A298535

Adjacent sequences: A199809 A199810 A199811 * A199813 A199814 A199815

Keyword

nonn,nice,more,hard

Author

Vladimir Reshetnikov, Nov 10 2011

Extensions

a(18)-a(20) from Robert G. Wilson v, Sep 15 2012

Status

approved