A036717 -id:A036717 - 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

A036726 G.f. satisfies A(x) = 1 + x*cycle_index(G,A(x)) where G = cyclic group of order 3 generated by (1,2,3)(4,5,6).

Original entry on oeis.org

1, 1, 2, 9, 46, 247, 1436, 8684, 54102, 345042, 2241014, 14771896, 98568908, 664518873, 4519394316, 30969650840, 213625862342, 1482134240438, 10335968352644, 72411026552273, 509383556655134, 3596650497366507, 25480925906761956

Offset: 0

N. J. A. Sloane

nonn

Cf. A036717-A036725.

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

A036719 G.f. satisfies A(x) = 1 + x*cycle_index(Cyclic(4), A(x)).

Original entry on oeis.org

1, 1, 1, 3, 7, 22, 65, 212, 697, 2372, 8179, 28703, 101851, 365393, 1322034, 4820378, 17691018, 65306700, 242317423, 903242615, 3380707920, 12700575742, 47874113728, 181013422393, 686341240781, 2609093456212, 9941953711409

Offset: 0

N. J. A. Sloane

nonn

Cf. A036717, A036718.

A036720 G.f. satisfies A(x) = 1 + x*cycle_index(Klein_4_group, A(x)).

Original entry on oeis.org

1, 1, 1, 4, 8, 27, 79, 270, 894, 3130, 11011, 39622, 143879, 528919, 1960248, 7323999, 27542451, 104194485, 396204388, 1513599583, 5806283770, 22356914550, 86376741339, 334752355281, 1300999638753, 5069411676111, 19800500391264

Offset: 0

N. J. A. Sloane

nonn

Cf. A036717-A036719.

A036723 G.f. satisfies A(x) = 1 + x*cycle_index(G,A(x)) where G = cyclic group of order 2 generated by (1,2)(3,4).

Original entry on oeis.org

1, 1, 2, 8, 30, 135, 622, 3032, 15134, 77506, 403780, 2135588, 11430910, 61815916, 337193808, 1853183376, 10251612034, 57037706410, 318965425380, 1791842232154, 10107161112356, 57221612791015, 325045726349906, 1852055247196164

Offset: 0

N. J. A. Sloane

nonn

Cf. A036717-A036722.

A036724 G.f. satisfies A(x) = 1 + x*cycle_index(G,A(x)) where G = cyclic group of order 2 generated by (1,2)(3,4)(5,6).

Original entry on oeis.org

1, 1, 3, 18, 109, 768, 5652, 43618, 346353, 2816526, 23321925, 196005552, 1667527836, 14333190427, 124283998707, 1085847441828, 9549523972105, 84471264138366, 751042470499425, 6708237169875867, 60164133936171522

Offset: 0

N. J. A. Sloane

nonn

Cf. A036717-A036723.

A036725 G.f. satisfies A(x) = 1 + x*cycle_index(G,A(x)) where G = cyclic group of order 2 generated by (1,2)(3,4)(5,6)(7,8).

Original entry on oeis.org

1, 1, 4, 32, 268, 2574, 26004, 274752, 2990412, 33321801, 378155340, 4355839608, 50792907100, 598432565856, 7112882558060, 85186232560504, 1026982086302284, 12453151958594288, 151785836438975264, 1858565360218893144, 22851521570687098564

Offset: 0

N. J. A. Sloane

nonn

Cf. A036717-A036724.

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

A036726 G.f. satisfies A(x) = 1 + x*cycle_index(G,A(x)) where G = cyclic group of order 3 generated by (1,2,3)(4,5,6).

Views

Author

Keywords

Crossrefs

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

A036719 G.f. satisfies A(x) = 1 + x*cycle_index(Cyclic(4), A(x)).

Views

Author

Keywords

Crossrefs

A036720 G.f. satisfies A(x) = 1 + x*cycle_index(Klein_4_group, A(x)).

Views

Author

Keywords

Crossrefs

A036723 G.f. satisfies A(x) = 1 + x*cycle_index(G,A(x)) where G = cyclic group of order 2 generated by (1,2)(3,4).

Views

Author

Keywords

Crossrefs

A036724 G.f. satisfies A(x) = 1 + x*cycle_index(G,A(x)) where G = cyclic group of order 2 generated by (1,2)(3,4)(5,6).

Views

Author

Keywords

Crossrefs

A036725 G.f. satisfies A(x) = 1 + x*cycle_index(G,A(x)) where G = cyclic group of order 2 generated by (1,2)(3,4)(5,6)(7,8).

Views

Author

Keywords

Crossrefs