A036720 -id:A036720 - cp's OEIS frontend

A036718 Number of rooted trees where each node has at most 4 children.

1, 1, 1, 2, 4, 9, 19, 45, 106, 260, 643, 1624, 4138, 10683, 27790, 72917, 192548, 511624, 1366424, 3666930, 9881527, 26730495, 72556208, 197562840, 539479354, 1477016717, 4053631757, 11149957667, 30732671572, 84871652538, 234802661446, 650684226827

Offset: 0

N. J. A. Sloane

			From _Joerg Arndt_, Feb 25 2017: (Start)
The a(5) = 9 rooted trees with 5 nodes and out-degrees <= 4 are:
:         level sequence    out-degrees (dots for zeros)
:     1:  [ 0 1 2 3 4 ]    [ 1 1 1 1 . ]
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]    [ 1 1 2 . . ]
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]    [ 1 2 1 . . ]
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]    [ 2 1 1 . . ]
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]    [ 1 3 . . . ]
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]    [ 2 2 . . . ]
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]    [ 2 1 . 1 . ]
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]    [ 3 1 . . . ]
:  O--o--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 ]    [ 4 . . . . ]
:  O--o
:  .--o
:  .--o
:  .--o
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
M. R. Bremner and H. A. Eigendy, Alternating quaternary algebra structures on irreducible representations of sl_2(C), Lin. Alg. Applic. 433 (2010) 1686-1705.
F. Ruskey, Information on Rooted Trees

Cf. A000081, A036717, A036719, A036720, A036721, A036722, A182378, A244372.
Cf. A292553, A292554, A292555, A292556.
Column k=4 of A299038.

A := 1; f := proc(n) global A; local A2,A3,A4; A2 := subs(x=x^2,A); A3 := subs(x=x^3,A); A4 := subs(x=x^4,A);
coeff(series( 1+x*( (A^4+3*A2^2+8*A*A3+6*A^2*A2+6*A4)/2 ), x, n+1), x,n); end;
for n from 1 to 50 do A := series(A+f(n)*x^n,x,n +1); od: A;

a = 1; f[n_] := Module[{a2, a3, a4}, a2 = a /. x -> x^2; a3 = a /. x -> x^3; a4 = a /. x -> x^4; Coefficient[ Series[ 1 + x*(a^4 + 3*a2^2 + 8*a*a3 + 6*a^2*a2 + 6*a4)/24, {x, 0, n + 1}] // Normal, x, n]]; For[n = 1, n <= 30, n++, a = Series[a + f[n]*x^n, {x, 0, n + 1}] // Normal]; CoefficientList[a, x] (* Jean-François Alcover, Jan 16 2013, after Maple *)
b[0, i_, t_, k_] = 1; m = 4; (* m = maximum children *)
b[n_,i_,t_,k_]:= b[n,i,t,k]= If[i<1,0,
   Sum[Binomial[b[i-1, i-1, k, k] + j-1, j]*
   b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
PrependTo[Table[b[n-1, n-1, m, m], {n, 1, 30}], 1] (* Robert A. Russell, Dec 27 2022 *)

G.f. satisfies A(x) = 1 + x*cycle_index(Sym(4), A(x)).
a(n) = Sum_{j=1..4} A244372(n,j) for n>0, a(0) = 1. - Alois P. Heinz, Sep 19 2017
a(n) / a(n+1) ~ 0.343520104570489046632074698738792654644751898257681287407149... - Robert A. Russell, Feb 11 2023

Better description from Frank Ruskey, Sep 23 2000

A036722 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(6), A(x)).

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 48, 114, 283, 710, 1816, 4690, 12267, 32338, 85978, 230080, 619521, 1676808, 4560286, 12454272, 34143682, 93928091, 259208006, 717375068, 1990625390, 5537142610, 15436744525, 43124847431, 120708508008, 338477040445, 950714584576

Offset: 0

N. J. A. Sloane

nonn

a(n) is also the number of rooted trees where each node has at most 6 children. [Patrick Devlin, Apr 29 2012]

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

Cf. A000081, A036717, A036718, A036719, A036720, A036721, A182378, A244372, A292553, A292554, A292555, A292556.

Column k=6 of A299038.

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
a:= n-> `if`(n=0, 1, b(n-1$2, 6$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 20 2017

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i < 1, 0, Sum[ Binomial[b[i - 1, i - 1, k, k] + j - 1, j]*b[n - i*j, i - 1, t - j, k], {j, 0, Min[t, n/i]}]]];
a[n_] := If[n == 0, 1, b[n - 1, n - 1, 6, 6]];
Table[a[n] , {n, 0, 35}] // Flatten (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

a(n) = Sum_{j=1..6} A244372(n,j) for n>0, a(0) = 1. - Alois P. Heinz, Sep 19 2017

a(n) / a(n+1) ~ 0.338887196052856714304749078960983936661485522864792573284374... - Robert A. Russell, Feb 11 2023

A036721 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(5), A(x)).

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 47, 112, 277, 693, 1766, 4547, 11852, 31146, 82534, 220149, 590834, 1593951, 4320723, 11761394, 32138301, 88121176, 242383729, 668607115, 1849194691, 5126800907, 14245679652, 39666239726, 110661514973, 309280533011, 865839831118

Offset: 0

N. J. A. Sloane

nonn

Also the number of rooted trees where each node has at most 5 children. [Patrick Devlin, Apr 30 2012]

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Joerg Arndt, The a(6) = 20 rooted trees with 5 nodes and out-degrees <= 5

Cf. A000081, A036717, A036718, A036719, A036720, A036722, A182378, A244372, A292553, A292554, A292555, A292556.

Column k=5 of A299038.

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
a:= n-> `if`(n=0, 1, b(n-1$2, 5$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 20 2017

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i < 1, 0, Sum[ Binomial[b[i - 1, i - 1, k, k] + j - 1, j]*b[n - i*j, i - 1, t - j, k], {j, 0, Min[t, n/i]}]]];
a[n_] := If[n == 0, 1, b[n - 1, n - 1, 5, 5]];
Table[a[n], {n, 0, 35}] // Flatten (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

a(n) = Sum_{j=1..5} A244372(n,j) for n>0, a(0) = 1. - Alois P. Heinz, Sep 19 2017

a(n) / a(n+1) ~ 0.340017469151060086823930137816585262710976835711484267209811... - Robert A. Russell, Feb 11 2023

A182378 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(7), A(x)).

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 48, 115, 285, 716, 1833, 4740, 12410, 32754, 87176, 233547, 629540, 1705809, 4644231, 12697500, 34848694, 95973026, 265142431, 734606478, 2040683413, 5682634446, 15859800889, 44355531103, 124290064228, 348904212741, 981082979409

Offset: 0

Michael Burkhart, Apr 26 2012

nonn

Number of rooted trees where each node has at most 7 children.

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

Cf. A000081, A036717, A036718, A036719, A036720, A036721, A036722, A244372, A292553, A292554, A292555, A292556.

Column k=7 of A299038.

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
a:= n-> `if`(n=0, 1, b(n-1$2, 7$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 20 2017

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i < 1, 0, Sum[ Binomial[ b[i-1, i-1, k, k] + j - 1, j]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]]];
a[n_] := If[n == 0, 1, b[n-1, n-1, 7, 7]];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jan 15 2018, after Alois P. Heinz *)

a(n) = Sum_{j=1..7} A244372(n,j) for n>0, a(0) = 1. - Alois P. Heinz, Sep 19 2017

a(n) / a(n+1) ~ 0.338512011286603947719604869750539045616436718225097926729820... - Robert A. Russell, Feb 11 2023

More terms from Patrick Devlin, Apr 29 2012

cp's OEIS Frontend

A036718 Number of rooted trees where each node has at most 4 children.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A036722 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(6), A(x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A036721 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(5), A(x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A182378 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(7), A(x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions