A000081 -id:A000081 - cp's OEIS frontend

A051491 Decimal expansion of Otter's rooted tree constant: lim_{n->inf} A000081(n+1)/A000081(n).

2, 9, 5, 5, 7, 6, 5, 2, 8, 5, 6, 5, 1, 9, 9, 4, 9, 7, 4, 7, 1, 4, 8, 1, 7, 5, 2, 4, 1, 2, 3, 1, 9, 4, 5, 8, 8, 3, 7, 5, 4, 9, 2, 3, 0, 4, 6, 6, 3, 5, 9, 6, 5, 9, 5, 3, 5, 0, 4, 7, 2, 4, 7, 8, 9, 0, 5, 9, 6, 4, 7, 3, 3, 1, 3, 9, 5, 7, 4, 9, 5, 1, 0, 8, 6, 6, 6, 8, 2, 8, 3, 6, 7, 6, 5, 8, 1, 3, 5, 2, 5, 3

Offset: 1

David Broadhurst

A000055(n) ~ A086308 * A051491^n * n^(-5/2), A000081(n) ~ A187770 * A051491^n * n^(-3/2). - Vaclav Kotesovec, Jan 04 2013

Analytic Combinatorics (Flajolet and Sedgewick, 2009, p. 481) has a wrong value of this constant (2.9955765856). - Vaclav Kotesovec, Jan 04 2013

			2.95576528565199497471481752412319458837549230466359659535...

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.

David Broadhurst, Resurgent Integer Sequences, Rutgers Experimental Math Seminar, Feb 06 2025; Slides.
Amirmohammad Farzaneh, Mihai-Alin Badiu, and Justin P. Coon, On Random Tree Structures, Their Entropy, and Compression, arXiv:2309.09779 [cs.IT], 2023.
S. R. Finch, Otter's Tree Enumeration Constants [Broken link]
S. R. Finch, Otter's Tree Enumeration Constants [Wayback Machine]
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, p. 481
Simon Plouffe, Tree-growth constant to 1800 digits
Eric Weisstein's World of Mathematics, Rooted Tree
Eric Weisstein's World of Mathematics, Tree
Index entries for sequences related to trees
Index entries for sequences related to rooted trees

Cf. A000081, A051492, A187770, A000055, A086308, A215978, A274082.

digits = 99; max = 250; s[n_, k_] := s[n, k] = a[n+1-k] + If[n < 2*k, 0, s[n-k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[k]*s[n-1, k]*k, {k, 1, n-1}]/(n-1); A[x_] := Sum[a[k]*x^k, {k, 0, max}]; eq = Log[c] == 1+Sum[A[c^-k]/k, {k, 2, max}]; alpha = c /. FindRoot[eq, {c, 3}, WorkingPrecision -> digits+5]; RealDigits[alpha, 10, digits] // First (* Jean-François Alcover, Sep 24 2014 *)

A358378 Numbers k such that the k-th standard ordered rooted tree is fully canonically ordered (counted by A000081).

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 15, 16, 17, 21, 25, 27, 29, 31, 32, 37, 41, 43, 49, 53, 57, 59, 61, 63, 64, 65, 73, 81, 85, 101, 105, 107, 113, 117, 121, 123, 125, 127, 128, 129, 137, 145, 165, 169, 171, 193, 201, 209, 213, 229, 233, 235, 241, 245, 249, 251

Offset: 1

Gus Wiseman, Nov 14 2022

nonn

The ordering of finitary multisets is first by length and then lexicographically. This is also the ordering used for Mathematica expressions.

We define the n-th standard ordered rooted tree to be obtained by taking the (n-1)-th composition in standard order (graded reverse-lexicographic, A066099) as root and replacing each part with its own standard ordered rooted tree. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.

			The terms together with their corresponding ordered rooted trees begin:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   7: (o(o))
   8: (ooo)
   9: ((oo))
  11: ((o)(o))
  13: (o((o)))
  15: (oo(o))
  16: (oooo)
  17: ((((o))))
  21: ((o)((o)))

Gus Wiseman, Statistics, classes, and transformations of standard compositions

These trees are counted by A000081.
A358371 and A358372 count leaves and nodes in standard ordered rooted trees.
Cf. A001263, A004249, A005043, A032027, A063895, A276625, A358373-A358377.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Select[Range[1000],FreeQ[srt[#],[_]?(!OrderedQ[#]&)]&]

A051573 INVERTi transform of A000081 = [1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486,...].

Original entry on oeis.org

1, 1, 1, 2, 3, 8, 16, 41, 98, 250, 631, 1646, 4285, 11338, 30135, 80791, 217673, 590010, 1606188, 4392219, 12055393, 33206321, 91752211, 254261363, 706465999, 1967743066, 5493195530, 15367129299, 43073007846, 120949992543, 340206026166, 958444631917

Offset: 0

N. J. A. Sloane

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
N. J. A. Sloane, Transforms

Cf. A052250, A000081.

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

b[n_] := b[n] = If[n < 2, n, Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}]/(n-1)]; a[n_] := a[n] = If[n < 0, -1, -Sum[a[n-i]*b[i+1], {i, 1, n+1}]]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Apr 16 2014, after Alois P. Heinz *)

a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148175241..., c = A187770 = 0.4399240125710253040409033914... . - Vaclav Kotesovec, Sep 06 2014

A216349 Triangle T(n,k) in which n-th row lists the values of the n-th derivative at x=1 of all functions that are representable as x^x^...^x with n x's and parentheses inserted in all possible ways; n>=1, 1<=k<=A000081(n).

Original entry on oeis.org

1, 2, 12, 9, 156, 100, 80, 56, 3160, 1880, 1180, 1420, 950, 1360, 890, 660, 480, 87990, 50496, 29682, 35382, 24042, 22008, 14928, 31968, 20268, 14988, 10848, 34974, 21474, 13314, 15114, 10974, 13014, 8874, 6534, 5094, 3218628, 1806476, 1021552, 588756, 1189132

Offset: 1

Alois P. Heinz, Sep 04 2012

The ordering of the functions is the same as in A215703 and is defined by the algorithm below.

			For n=4 the A000081(4) = 4 functions and their 4th derivatives at x=1 are x^(x^3)->156, x^(x^x*x)->100, x^(x^(x^2))->80, x^(x^(x^x))->56.
Triangle T(n,k) begins:
:     1;
:     2;
:    12,     9;
:   156,   100,    80,    56;
:  3160,  1880,  1180,  1420,   950,  1360,   890,   660,   480;
: 87990, 50496, 29682, 35382, 24042, 22008, 14928, 31968, 20268, ...

Alois P. Heinz, Rows n = 1..12, flattened

First column gives: A216351.
Last elements of rows give: A033917.
A version with sorted row elements is: A216350.
Rows sums give: A216281.
Cf. A000081, A215703.

with(combinat):
F:= proc(n) F(n):= `if`(n<2, [x$n], map(h->x^h, g(n-1, n-1))) end:
g:= proc(n, i) option remember; `if`(n=0 or i=1, [x^n],
     `if`(i<1, [], [seq(seq(seq(mul(F(i)[w[t]-t+1], t=1..j)*v,
      w=choose([$1..nops(F(i))+j-1], j)), v=g(n-i*j, i-1)), j=0..n/i)]))
    end:
T:= n-> map(f-> n!*coeff(series(subs(x=x+1, f), x, n+1), x, n), F(n))[]:
seq(T(n), n=1..7);

A216350 Triangle T(n,k) in which n-th row lists in increasing order the values of the n-th derivative at x=1 of all functions that are representable as x^x^...^x with n x's and parentheses inserted in all possible ways; n>=1, 1<=k<=A000081(n).

Original entry on oeis.org

1, 2, 9, 12, 56, 80, 100, 156, 480, 660, 890, 950, 1180, 1360, 1420, 1880, 3160, 5094, 6534, 8874, 10848, 10974, 13014, 13314, 14928, 14988, 15114, 20268, 21474, 22008, 24042, 29682, 31968, 34974, 35382, 50496, 87990, 65534, 78134, 102494, 131684, 141974

Offset: 1

Alois P. Heinz, Sep 04 2012

			For n=4 the A000081(4) = 4 functions and their 4th derivatives at x=1 are x^(x^3)->156, x^(x^x*x)->100, x^(x^(x^2))->80, x^(x^(x^x))->56 => 4th row = [56, 80, 100, 156].
Triangle T(n,k) begins:
:    1;
:    2;
:    9,   12;
:   56,   80,  100,   156;
:  480,  660,  890,   950,  1180,  1360,  1420,  1880,  3160;
: 5094, 6534, 8874, 10848, 10974, 13014, 13314, 14928, 14988, 15114, ...

Alois P. Heinz, Rows n = 1..12, flattened

First column gives: A033917.
Last elements of rows give: A216351.
A version with different ordering of row elements is: A216349.
Rows sums give: A216281.
Cf. A000081, A215703.

with(combinat):
F:= proc(n) F(n):= `if`(n<2, [x$n], map(h->x^h, g(n-1, n-1))) end:
g:= proc(n, i) option remember; `if`(n=0 or i=1, [x^n],
     `if`(i<1, [], [seq(seq(seq(mul(F(i)[w[t]-t+1], t=1..j)*v,
      w=choose([$1..nops(F(i))+j-1], j)), v=g(n-i*j, i-1)), j=0..n/i)]))
    end:
T:= n-> sort(map(f-> n!*coeff(series(subs(x=x+1, f)
                 , x, n+1), x, n), F(n)))[]:
seq(T(n), n=1..7);

A216648 Triangle T(n,k) in which n-th row lists in increasing order all positive integers with a representation as totally balanced 2n digit binary string without totally balanced proper prefixes such that all consecutive totally balanced substrings are in nondecreasing order; n>=1, 1<=k<=A000081(n).

Original entry on oeis.org

2, 12, 52, 56, 212, 216, 232, 240, 852, 856, 872, 880, 920, 936, 944, 976, 992, 3412, 3416, 3432, 3440, 3480, 3496, 3504, 3536, 3552, 3688, 3696, 3752, 3760, 3792, 3808, 3888, 3920, 3936, 4000, 4032, 13652, 13656, 13672, 13680, 13720, 13736, 13744, 13776

Offset: 1

Alois P. Heinz, Sep 12 2012

There is a simple bijection between the elements of row n and the rooted trees with n nodes. Each matching pair (1,0) in the binary string representation encodes a node, each totally balanced substring encodes a list of subtrees.

			856 is element of row 5, the binary string representation (with totally balanced substrings enclosed in parentheses) is (1(10)(10)(1(10)0)0).  The encoded rooted tree is:
.    o
.   /|\
.  o o o
.      |
.      o
Triangle T(n,k) begins:
2;
12;
52,     56;
212,   216,  232,  240;
852,   856,  872,  880,  920,  936,  944,  976,  992;
3412, 3416, 3432, 3440, 3480, 3496, 3504, 3536, 3552, 3688, 3696, ...
Triangle T(n,k) in binary:
10;
1100;
110100,       111000;
11010100,     11011000,     11101000,     11110000;
1101010100,   1101011000,   1101101000,   1101110000,   1110011000, ...
110101010100, 110101011000, 110101101000, 110101110000, 110110011000, ...

Alois P. Heinz, Rows n = 1..12, flattened

First column gives: A080675.
Last elements of rows give: A020522.
Row lengths are: A000081.
Subsequence of A057547, A081292.
Cf. A061773, A216349, A216350, A216649.

F:= proc(n) option remember; `if`(n=1, [10], sort(map(h->
      parse(cat(1, sort(h)[], 0)), g(n-1, n-1)))) end:
g:= proc(n, i) option remember; `if`(i=1, [[10$n]], [seq(seq(seq(
      [seq (F(i)[w[t]-t+1], t=1..j),v[]], w=combinat[choose](
      [$1..nops(F(i))+j-1], j)), v=g(n-i*j, i-1)), j=0..n/i)])
    end:
b:= proc(n) local h, i, r; h, r:= n, 0; for i from 0
      while h>0 do r:= r+2^i*irem(h, 10, 'h') od; r
    end:
T:= proc(n) option remember; map(b, F(n))[] end:
seq(T(n), n=1..7);

T(n,k) = A216649(n-1,k)*2 + 2^(2*n-1) for n>1.

A051420 Numbers k such that A000081(k) is prime.

Original entry on oeis.org

3, 10, 15, 343, 387, 1087, 2981, 96761

Offset: 1

David Broadhurst

A000081(2981) = O(10^1400) is only a probably prime. No more terms < 6000.
No more terms < 40000. - Vaclav Kotesovec, Jul 07 2020
A000081(96761) is a probable prime. No other terms < 100000. - Mathieu Gouttenoire, Oct 08 2021

Cf. A000081, A119642, A185667, A336039.

a(8) from Mathieu Gouttenoire, Oct 08 2021

A100034 Bisection of A000081 (even part).

Original entry on oeis.org

0, 1, 4, 20, 115, 719, 4766, 32973, 235381, 1721159, 12826228, 97055181, 743724984, 5759636510, 45007066269, 354426847597, 2809934352700, 22409533673568, 179655930440464, 1447023384581029, 11703780079612453, 95020085893954917, 774088023431472074

Offset: 0

N. J. A. Sloane, Nov 20 2004

Alois P. Heinz, Table of n, a(n) for n = 0..400

Cf. A000081, A100427, A299098.

with(numtheory):
b:= proc(n) option remember; local d, j; `if`(n<2, n,
      (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
a:= n-> b(2*n):
seq(a(n), n=0..50);  # Alois P. Heinz, May 16 2013

b[n_] := b[n] = If[n <= 1, n, Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}]/(n-1)]; a[n_] := b[2*n]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 19 2014, after Alois P. Heinz *)

More terms from Joshua Zucker, May 12 2006

A280788 Convolution of A000081 and A027852, shifted by 3 leading zeros.

Original entry on oeis.org

1, 2, 6, 15, 41, 106, 284, 750, 2010, 5382, 14523, 39290, 106854, 291552, 798675, 2194828, 6051153, 16730373, 46383002, 128910484, 359115067, 1002575810, 2804667061, 7860780578, 22070885735, 62071872704, 174842835886, 493217417610

Offset: 0

N. J. A. Sloane, Jan 20 2017

nonn

R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016. See (71).

Cf. A269800, A280786, A280787, A027852.

A280788 := proc(N::integer)
    if N = 0 then
        1;
    else
        add(A000081(Nprime+1)*A027852(N-Nprime+2),Nprime=0..N) ;
    end if;
end proc:
seq(A280788(n),n=0..30) ; # R. J. Mathar, Mar 06 2017

a81[n_] := a81[n] = If[n <= 1, n, Sum[a81[n - j]*DivisorSum[j, #*a81[#]&], {j, n - 1}]/(n - 1)];
A027852[n_] := Module[{dh = 0, np}, For[np = 0, np <= n, np++, dh = a81[np] * a81[n - np] + dh]; If[EvenQ[n], dh = a81[n/2] + dh]; dh/2];
A280788[n_] := If[n == 0, 1, Sum[a81[np+1]*A027852[n-np+2], {np, 0, n}]];
Table[A280788[n], {n, 0, 27}] (* Jean-François Alcover, Nov 23 2017, from Maple *)

A100427 Bisection of A000081 (odd part).

Original entry on oeis.org

1, 2, 9, 48, 286, 1842, 12486, 87811, 634847, 4688676, 35221832, 268282855, 2067174645, 16083734329, 126186554308, 997171512998, 7929819784355, 63411730258053, 509588049810620, 4113254119923150, 33333125878283632, 271097737169671824, 2212039245722726118

Offset: 0

N. J. A. Sloane, Nov 20 2004

Alois P. Heinz, Table of n, a(n) for n = 0..400

Cf. A000081, A100034, A299113.

with(numtheory):
b:= proc(n) option remember; local d, j; `if`(n<2, n,
      (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
a:= n-> b(2*n+1):
seq(a(n), n=0..50);  # Alois P. Heinz, May 16 2013

b[n_] := b[n] = If[n <= 1, n, Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}]/(n-1)]; a[n_] := b[2*n+1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 19 2014, after Alois P. Heinz *)

More terms from Joshua Zucker, May 12 2006

cp's OEIS Frontend

A051491 Decimal expansion of Otter's rooted tree constant: lim_{n->inf} A000081(n+1)/A000081(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A358378 Numbers k such that the k-th standard ordered rooted tree is fully canonically ordered (counted by A000081).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A051573 INVERTi transform of A000081 = [1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486,...].

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A216349 Triangle T(n,k) in which n-th row lists the values of the n-th derivative at x=1 of all functions that are representable as x^x^...^x with n x's and parentheses inserted in all possible ways; n>=1, 1<=k<=A000081(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A216350 Triangle T(n,k) in which n-th row lists in increasing order the values of the n-th derivative at x=1 of all functions that are representable as x^x^...^x with n x's and parentheses inserted in all possible ways; n>=1, 1<=k<=A000081(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A051420 Numbers k such that A000081(k) is prime.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A100034 Bisection of A000081 (even part).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A280788 Convolution of A000081 and A027852, shifted by 3 leading zeros.

Views