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