A003018 -id:A003018 - cp's OEIS frontend

A255170 a(n) = A087803(n) - n + 1.

1, 1, 2, 5, 13, 32, 79, 193, 478, 1196, 3037, 7802, 20287, 53259, 141069, 376449, 1011295, 2732453, 7421128, 20247355, 55469186, 152524366, 420807220, 1164532203, 3231706847, 8991343356, 25075077684, 70082143952, 196268698259, 550695545855, 1547867058852

Offset: 1

Vladimir Reshetnikov, Feb 15 2015

Conjectured extension of 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. So far all known terms of A199812 (that is, 20 of them) coincide with this sequence. It is conjectured that A199812 is actually identical to this sequence, but it remains unproved, and is computationally difficult to check for n > 20.

			a(4) = 1 - 4 + Sum_{k=1..4} A000081(k) = 1 - 4 + 1 + 1 + 2 + 4 = 5.
a(5) = 1 - 5 + Sum_{k=1..5} A000081(k) = 1 - 5 + 1 + 1 + 2 + 4 + 9 = 13.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
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.
Eric Weisstein's World of Mathematics, Rooted Tree.

Cf. A199812 (conjectured to be identical), A087803, A000081, A174145 (2nd differences), A005348, A002845, A198683, A187770, A051491.

with(numtheory):
t:= proc(n) option remember; `if`(n<2, n, (add(add(
      d*t(d), d=divisors(j))*t(n-j), j=1..n-1))/(n-1))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
      add(b(n-i*j, i-1)*binomial(t(i)+j-1, j), j=0..n/i)))
    end:
a:= proc(n) option remember; `if`(n<3, 1,
      b(n-1$2) +2*a(n-1) -a(n-2))
    end:
seq(a(n), n=1..40);  # Alois P. Heinz, Feb 17 2015

t[1] = a[1] = 1; t[n_] := t[n] = Sum[k t[k] t[n - k m]/(n-1), {k, n}, {m, (n-1)/k}]; a[n_] := a[n] = a[n-1] + t[n] - 1; Table[a[n], {n, 40}] (* Vladimir Reshetnikov, Aug 12 2016 *)

a(n) = 1 - n + Sum_{k=1..n} A000081(k).
Recurrence: a(1) = 1, a(n+1) = a(n) + A000081(n+1) - 1.
Recurrence: a(1) = a(2) = 1, a(n) = A174145(n-1) + 2*a(n-1) - a(n-2).
Asymptotics: a(n) ~ c * d^n / n^(3/2), where c = A187770 / (1 - 1 / A051491) = 0.664861... and d = A051491 = 2.955765...

Simpler definition and program in terms of A000081. - Vladimir Reshetnikov, Aug 12 2016

Renamed. - Vladimir Reshetnikov, Aug 23 2016

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.

Original entry on oeis.org

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

Offset: 1

Vladimir Reshetnikov, Nov 10 2011

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.

			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.

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

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

(* 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}]

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

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

A215796 Number of distinct values taken by 7th derivative of x^x^...^x (with n x's and parentheses inserted in all possible ways) at x=1.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 48, 115, 283, 691, 1681, 3988, 9241, 20681, 44217, 89644

Offset: 1

Alois P. Heinz, Aug 24 2012

			a(4) = 4 because the A000108(3) = 5 possible parenthesizations of x^x^x^x lead to 4 different values of the 7th derivative at x=1: (x^(x^(x^x))) -> 26054; ((x^x)^(x^x)), ((x^(x^x))^x) -> 41090; (x^((x^x)^x)) -> 47110; (((x^x)^x)^x) -> 70098.

Column k=7 of A216368.

Cf. A000081 (distinct functions), A000108 (parenthesizations), A000012 (first derivatives), A028310 (2nd derivatives), A199085 (3rd derivatives), A199205 (4th derivatives), A199296 (5th derivatives), A199883 (6th derivatives), A002845, A003018, A003019, A145545, A145546, A145547, A145548, A145549, A145550, A082499, A196244, A198683, A215703, A215837.

T:= proc(n) T(n):=`if`(n=1, [x], map(h-> x^h, g(n-1$2))) end:
g:= proc(n, i) option remember; `if`(i=1, [x^n], [seq(seq(
      seq(mul(T(i)[w[t]-t+1], t=1..j)*v, v=g(n-i*j, i-1)), w=
      combinat[choose]([$1..nops(T(i))+j-1], j)), j=0..n/i)])
    end:
f:= proc() local i, l; i, l:= 0, []; proc(n) while n>
      nops(l) do i:= i+1; l:= [l[], T(i)[]] od; l[n] end
    end():
a:= n-> nops({map(f-> 7!*coeff(series(subs(x=x+1, f), x, 8), x, 7), T(n))[]}):
seq(a(n), n=1..12);

A215971 Number of distinct values taken by 8th derivative of x^x^...^x (with n x's and parentheses inserted in all possible ways) at x=1.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 48, 115, 286, 717, 1815, 4574, 11505, 28546, 69705, 166010

Offset: 1

Alois P. Heinz, Aug 29 2012

			a(4) = 4 because the A000108(3) = 5 possible parenthesizations of x^x^x^x lead to 4 different values of the 8th derivative at x=1: (x^(x^(x^x))) -> 269128; ((x^x)^(x^x)), ((x^(x^x))^x) -> 382520; (x^((x^x)^x)) -> 511216; (((x^x)^x)^x) -> 646272.

Cf. A000081 (distinct functions), A000108 (parenthesizations), A000012 (first derivatives), A028310 (2nd derivatives), A199085 (3rd derivatives), A199205 (4th derivatives), A199296 (5th derivatives), A199883 (6th derivatives), A002845, A003018, A003019, A145545, A145546, A145547, A145548, A145549, A145550, A082499, A196244, A198683, A215703, A215838. Column k=8 of A216368.

# load programs from A215703, then:
a:= n-> nops({map(f-> 8!*coeff(series(subs(x=x+1, f),
                  x, 9), x, 8), T(n))[]}):
seq(a(n), n=1..10);

A216062 Number of distinct values taken by 9th derivative of x^x^...^x (with n x's and parentheses inserted in all possible ways) at x=1.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1838, 4734, 12247, 31617, 81208

Offset: 1

Alois P. Heinz, Aug 31 2012

a(4) = 4 because the A000108(3) = 5 possible parenthesizations of x^x^x^x lead to 4 different values of the 9th derivative at x=1: (x^(x^(x^x))) -> 3010680; ((x^x)^(x^x)), ((x^(x^x))^x) -> 3863808; (x^((x^x)^x)) -> 6019416; (((x^x)^x)^x) -> 6333336.

Cf. A000081 (distinct functions), A000108 (parenthesizations), A000012 (first derivatives), A028310 (2nd derivatives), A199085 (3rd derivatives), A199205 (4th derivatives), A199296 (5th derivatives), A199883 (6th derivatives), A002845, A003018, A003019, A145545, A145546, A145547, A145548, A145549, A145550, A082499, A196244, A198683, A215703, A215839. Column k=9 of A216368.

# load programs from A215703, then:
a:= n-> nops({map(f-> 9!*coeff(series(subs(x=x+1, f),
                  x, 10), x, 9), T(n))[]}):
seq(a(n), n=1..11);

A216403 Number of distinct values taken by 10th derivative of x^x^...^x (with n x's and parentheses inserted in all possible ways) at x=1.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4763, 12452, 32711, 86239

Offset: 1

Alois P. Heinz, Sep 06 2012

nonn

			a(4) = 4 because the A000108(3) = 5 possible parenthesizations of x^x^x^x lead to 4 different values of the 10th derivative at x=1: (x^(x^(x^x))) -> 37616880; ((x^x)^(x^x)), ((x^(x^x))^x) -> 42409440; (x^((x^x)^x)) -> 77899320; (((x^x)^x)^x) -> 66712680.

Cf. A000081 (distinct functions), A000108 (parenthesizations), A000012 (first derivatives), A028310 (2nd derivatives), A199085 (3rd derivatives), A199205 (4th derivatives), A199296 (5th derivatives), A199883 (6th derivatives), A002845, A003018, A003019, A145545, A145546, A145547, A145548, A145549, A145550, A082499, A196244, A198683, A215703, A215840. Column k=10 of A216368.

# load programs from A215703, then:
a:= n-> nops({map(f-> 10!*coeff(series(subs(x=x+1, f),
                  x, 11), x, 10), T(n))[]}):
seq(a(n), n=1..11);

A003006 Number of n-level ladder expressions with A001622.

Original entry on oeis.org

1, 1, 2, 3, 7, 15, 35, 81, 195, 473, 1170, 2920, 7378, 18787, 48242, 124658, 324095, 846872, 2223352, 5861011, 15508423, 41173560, 109648734

Offset: 1

N. J. A. Sloane

Number of distinct values taken by phi^phi^...^phi (with n phi's and parentheses inserted in all possible ways), where phi = A001622 = (1 + sqrt(5))/2 is the golden ratio. - Vladimir Reshetnikov, Mar 05 2019

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis, Amer. Math. Monthly 80 (8) (1973), 868-876.
R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis. (annotated cached copy)
Index entries for sequences related to parenthesizing

Cf. A001622, A002845, A082499, A052321 (first 10 terms match), A198683, A199812.

ClearAll[phi, t, a]; t[1] = {0}; t[n_Integer] := t[n] = DeleteDuplicates[Flatten[Table[Outer[phi^#1 + #2 &, t[k], t[n - k]], {k, n - 1}]] /. phi^k_Integer :> Fibonacci[k] phi + Fibonacci[k - 1]]; a[n_Integer] := a[n] = Length[t[n]]; Table[a[n], {n, 23}]

a(10)-a(23) added by Vladimir Reshetnikov, Mar 05 2019

A003007 Erroneous version of A082499.

Original entry on oeis.org

1, 1, 2, 4, 8, 17, 38, 89, 208

Offset: 1

dead

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis, Amer. Math. Monthly 80 (8) (1973), 868-876.
R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis. (annotated cached copy)

A003008 Number of n-level ladder expressions with A030798.

Original entry on oeis.org

1, 1, 2, 4, 8, 17, 39, 90, 213

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis, Amer. Math. Monthly 80 (8) (1973), 868-876.
R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis. (annotated cached copy)
Index entries for sequences related to parenthesizing

Cf. A082499.

A297074 Number of ways of inserting parentheses in x^x^...^x (with n x's) whose result is an integer where x = sqrt(2).

Original entry on oeis.org

0, 0, 1, 1, 2, 5, 10, 23, 55

Offset: 1

Jon E. Schoenfield, Dec 24 2017

The largest value that can be obtained by inserting parentheses in x^x^x^x^x^x^x^x^x (9 x's), where x = sqrt(2), is x^(x^((((((x^x)^x)^x)^x)^x)^x)) = 2^128 = 340282366920938463463374607431768211456; this is one of the a(9) = 55 ways of inserting parentheses in x^x^x^x^x^x^x^x^x that yield an integer value.

			With x = sqrt(2),
x = 1.414213... is not an integer, so a(1) = 0;
x^x = 1.632526... is not an integer, so a(2) = 0.
(x^x)^x = 2 is an integer, but x^(x^x) = 1.760839... is not, so a(3) = 1;
((x^x)^x)^x, (x^x)^(x^x), (x^(x^x))^x, and x^(x^(x^x)) are noninteger values, but x^((x^x)^x) = 2, so a(4) = 1;
the only ways of inserting parentheses in x^x^x^x^x that yield integer values are x^(x^((x^x)^x)) = 2 and (((x^x)^x)^x)^x = 4, so a(5) = 2.

R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis, Amer. Math. Monthly 80 (8) (1973), 868-876.
R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis (annotated cached copy, with permission)
Index entries for sequences related to parenthesizing

Cf. A002845, A055113, A082499, A198683.

With[{x = Sqrt@ 2}, Array[Count[#, ?IntegerQ] &@ Map[ToExpression@ StringReplace[ToString@ #, {"{" -> "(", "}" -> ")", "," -> "^"}] &, Groupings[#, 2] /. _Integer -> x] &, 9]] (* _Michael De Vlieger, Dec 24 2017 *)

cp's OEIS Frontend

A255170 a(n) = A087803(n) - n + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A215796 Number of distinct values taken by 7th derivative of x^x^...^x (with n x's and parentheses inserted in all possible ways) at x=1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

A215971 Number of distinct values taken by 8th derivative of x^x^...^x (with n x's and parentheses inserted in all possible ways) at x=1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

A216062 Number of distinct values taken by 9th derivative of x^x^...^x (with n x's and parentheses inserted in all possible ways) at x=1.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

A216403 Number of distinct values taken by 10th derivative of x^x^...^x (with n x's and parentheses inserted in all possible ways) at x=1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

A003006 Number of n-level ladder expressions with A001622.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A003007 Erroneous version of A082499.

Views

Author

Keywords

References

Links

A003008 Number of n-level ladder expressions with A030798.

Views

Author

Keywords

References