OFFSET
1,3
COMMENTS
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
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