This site is supported by donations to The OEIS Foundation.

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