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

 

Logo


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

%I

%S 1,1,2,5,13,32,79,193,478,1196,3037,7802,20287,53259,141069,376449,

%T 1011295,2732453,7421128,20247355

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

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

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

%C Conjectured extension of this sequence is given by A255170.

%H Libor Behounek, <a href="http://mujweb.cz/behounek/logic/papers/ordcalc/index.html">Ordinal Calculator</a>

%H R. K. Guy and J. L. Selfridge, <a href="/A003018/a003018.pdf">The nesting and roosting habits of the laddered parenthesis</a>

%H MathOverflow, <a href="http://mathoverflow.net/q/103411/9550">A discussion related to this sequence</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/OrdinalNumber.html">Ordinal Number</a>

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

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

%t (* Slow exhaustive search *)

%t _ \[Precedes] {} = False;

%t {} \[Precedes] {__} = True;

%t {a_ \[Diamond] _, ___} \[Precedes] {b_ \[Diamond] _, ___} := a \[Precedes] b /; a =!= b;

%t {a_ \[Diamond] m_, ___} \[Precedes] {a_ \[Diamond] n_, ___} := m < n /; m != n;

%t {z_, x___} \[Precedes] {z_, y___} := {x} \[Precedes] {y};

%t m_ \[CirclePlus] {} := m;

%t {} \[CirclePlus] n_ := n;

%t {x___, a_ \[Diamond] m_} \[CirclePlus] {a_ \[Diamond] n_, y___} := {x, a \[Diamond] (m + n), y};

%t {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}];

%t {} \[CircleTimes] _ = {};

%t _ \[CircleTimes] {} = {};

%t {a_ \[Diamond] m_, x___} \[CircleTimes] {b_ \[Diamond] n_} := If[b === {}, {a \[Diamond] (m n), x}, {(a \[CirclePlus] b) \[Diamond] n}];

%t x_ \[CircleTimes] {y_, z__} := x \[CircleTimes] {y} \[CirclePlus] x \[CircleTimes] {z};

%t f[1] = {{{} \[Diamond] 1}};

%t f[n_] := f[n] = Union[Flatten[Table[Outer[#1 \[CircleTimes] {#2 \[Diamond] 1} &, f[k], f[n - k], 1], {k, n - 1}], 2]];

%t Table[Length[f[n]], {n, 1, 17}]

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

%K nonn,nice,more,hard

%O 1,3

%A _Vladimir Reshetnikov_, Nov 10 2011

%E a(18)-a(20) from _Robert G. Wilson v_, Sep 15 2012

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 October 22 09:57 EDT 2018. Contains 316433 sequences. (Running on oeis4.)