cp's OEIS Frontend

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

%I A036718 #41 Feb 12 2023 10:21:29
%S A036718 1,1,1,2,4,9,19,45,106,260,643,1624,4138,10683,27790,72917,192548,
%T A036718 511624,1366424,3666930,9881527,26730495,72556208,197562840,539479354,
%U A036718 1477016717,4053631757,11149957667,30732671572,84871652538,234802661446,650684226827
%N A036718 Number of rooted trees where each node has at most 4 children.
%H A036718 Alois P. Heinz, <a href="/A036718/b036718.txt">Table of n, a(n) for n = 0..1000</a>
%H A036718 M. R. Bremner and H. A. Eigendy, <a href="https://doi.org/10.1016/j.laa.2010.06.014">Alternating quaternary algebra structures on irreducible representations of sl_2(C)</a>, Lin. Alg. Applic. 433 (2010) 1686-1705.
%H A036718 F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/tree/RootedTree.html">Information on Rooted Trees</a>
%F A036718 G.f. satisfies A(x) = 1 + x*cycle_index(Sym(4), A(x)).
%F A036718 a(n) = Sum_{j=1..4} A244372(n,j) for n>0, a(0) = 1. - _Alois P. Heinz_, Sep 19 2017
%F A036718 a(n) / a(n+1) ~ 0.343520104570489046632074698738792654644751898257681287407149... - _Robert A. Russell_, Feb 11 2023
%e A036718 From _Joerg Arndt_, Feb 25 2017: (Start)
%e A036718 The a(5) = 9 rooted trees with 5 nodes and out-degrees <= 4 are:
%e A036718 :         level sequence    out-degrees (dots for zeros)
%e A036718 :     1:  [ 0 1 2 3 4 ]    [ 1 1 1 1 . ]
%e A036718 :  O--o--o--o--o
%e A036718 :
%e A036718 :     2:  [ 0 1 2 3 3 ]    [ 1 1 2 . . ]
%e A036718 :  O--o--o--o
%e A036718 :        .--o
%e A036718 :
%e A036718 :     3:  [ 0 1 2 3 2 ]    [ 1 2 1 . . ]
%e A036718 :  O--o--o--o
%e A036718 :     .--o
%e A036718 :
%e A036718 :     4:  [ 0 1 2 3 1 ]    [ 2 1 1 . . ]
%e A036718 :  O--o--o--o
%e A036718 :  .--o
%e A036718 :
%e A036718 :     5:  [ 0 1 2 2 2 ]    [ 1 3 . . . ]
%e A036718 :  O--o--o
%e A036718 :     .--o
%e A036718 :     .--o
%e A036718 :
%e A036718 :     6:  [ 0 1 2 2 1 ]    [ 2 2 . . . ]
%e A036718 :  O--o--o
%e A036718 :     .--o
%e A036718 :  .--o
%e A036718 :
%e A036718 :     7:  [ 0 1 2 1 2 ]    [ 2 1 . 1 . ]
%e A036718 :  O--o--o
%e A036718 :  .--o--o
%e A036718 :
%e A036718 :     8:  [ 0 1 2 1 1 ]    [ 3 1 . . . ]
%e A036718 :  O--o--o
%e A036718 :  .--o
%e A036718 :  .--o
%e A036718 :
%e A036718 :     9:  [ 0 1 1 1 1 ]    [ 4 . . . . ]
%e A036718 :  O--o
%e A036718 :  .--o
%e A036718 :  .--o
%e A036718 :  .--o
%e A036718 (End)
%p A036718 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);
%p A036718 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;
%p A036718 for n from 1 to 50 do A := series(A+f(n)*x^n,x,n +1); od: A;
%t A036718 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 *)
%t A036718 b[0, i_, t_, k_] = 1; m = 4; (* m = maximum children *)
%t A036718 b[n_,i_,t_,k_]:= b[n,i,t,k]= If[i<1,0,
%t A036718    Sum[Binomial[b[i-1, i-1, k, k] + j-1, j]*
%t A036718    b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
%t A036718 PrependTo[Table[b[n-1, n-1, m, m], {n, 1, 30}], 1] (* _Robert A. Russell_, Dec 27 2022 *)
%Y A036718 Cf. A000081, A036717, A036719, A036720, A036721, A036722, A182378, A244372.
%Y A036718 Cf. A292553, A292554, A292555, A292556.
%Y A036718 Column k=4 of A299038.
%K A036718 nonn,easy,nice
%O A036718 0,4
%A A036718 _N. J. A. Sloane_
%E A036718 Better description from _Frank Ruskey_, Sep 23 2000