login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 2
1, 1, 2, 5, 13, 32, 79, 193, 478, 1196, 3037, 7802, 20287, 53259, 141069, 376449, 1011295, 2732453, 7421128, 20247355 (list; graph; refs; listen; history; text; internal format)
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 A110320

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 15 03:08 EST 2017. Contains 296020 sequences.