1,1

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

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

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

2.95576528565199497471481752412319458837549230466359659535...

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 *)

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

nonn,nice,cons

approved

1,2

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.

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

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

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[#]&)]&]

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.

Gus Wiseman, Nov 14 2022

approved

0,4

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

N. J. A. Sloane, Transforms

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

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 *)

Cf. A052250, A000081.

approved

1,2

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

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

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

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);

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.

nonn,look,tabf

Alois P. Heinz, Sep 04 2012

approved

1,2

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

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

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);

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.

nonn,tabf

Alois P. Heinz, Sep 04 2012

approved

1,1

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.

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

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

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

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);

First column gives: A080675.

Last elements of rows give: A020522.

Row lengths are: A000081.

Subsequence of A057547, A081292.

Cf. A061773, A216349, A216350, A216649.

nonn,tabf

Alois P. Heinz, Sep 12 2012

approved

1,1

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.

nonn,more

a(8) from Mathieu Gouttenoire, Oct 08 2021

approved

0,3

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

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 *)

Cf. A000081, A100427, A299098.

nonn,easy

N. J. A. Sloane, Nov 20 2004

More terms from Joshua Zucker, May 12 2006

approved

0,2

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

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 *)

Cf. A269800, A280786, A280787, A027852.

N. J. A. Sloane, Jan 20 2017

approved

0,2

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

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 *)

Cf. A000081, A100034, A299113.

nonn,easy

N. J. A. Sloane, Nov 20 2004

More terms from Joshua Zucker, May 12 2006

approved