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

Links

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

Formula

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

Example

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)

Maple

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;

Mathematica

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

Crossrefs

Cf. A000081, A036717, A036719, A036720, A036721, A036722, A182378, A244372.

Cf. A292553, A292554, A292555, A292556.

Column k=4 of A299038.

Sequence in context: A291648 A036613 A036614 * A372102 A134964 A318798

Adjacent sequences: A036715 A036716 A036717 * A036719 A036720 A036721

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Better description from Frank Ruskey, Sep 23 2000

Status

approved