cp's OEIS Frontend

A036650 Number of 5-valent trees with n nodes.

%I A036650 #28 Feb 12 2023 10:21:09
%S A036650 1,1,1,1,2,3,6,10,21,42,94,204,473,1098,2633,6353,15641,38789,97416,
%T A036650 246410,628726,1614292,4171955,10839366,28308678,74266477,195667533,
%U A036650 517504253,1373640355,3658205088,9772510063,26181295237,70330621171
%N A036650 Number of 5-valent trees with n nodes.
%H A036650 Andrew Howroyd, <a href="/A036650/b036650.txt">Table of n, a(n) for n = 0..500</a>
%H A036650 R. Otter, <a href="http://www.jstor.org/stable/1969046">The number of trees</a>, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
%H A036650 E. M. Rains and N. J. A. Sloane, <a href="https://cs.uwaterloo.ca/journals/JIS/cayley.html">On Cayley's Enumeration of Alkanes (or 4-Valent Trees).</a>, J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
%H A036650 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A036650 a(n) = A036648(n) + A036649(n) for n > 0.
%F A036650 G.f.: B(x) - cycle_index(S2,-B(x)) + x * cycle_index(S5,B(x)) = B(x) - (B(x)^2 - B(x^2)) / 2 + x * (B(x)^5 + 10*B(x)^3*B(x^2) + 15*B(x)*B(x^2)^2 + 20*B(x)^2*B(x^3) + 20*B(x^2)*B(x^3) + 30*B(x)*B(x^4) + 24*B(x^5)) / 120, where B(x) = 1 + x * cycle_index(S4,B(x)) = 1 + x * (B(x)^4 + 6*B(x)^2*B(x^2) + 8*B(x)*B(x^3) + 3*B(x^2)^2 + 6*B(x^4)) / 24 is the generating function for A036718. - _Robert A. Russell_, Jan 19 2023
%t A036650 n = 30; (* algorithm from Rains and Sloane *)
%t A036650 S4[f_,h_,x_] := f[h,x]^4/24 + f[h,x]^2 f[h,x^2]/4 + f[h,x] f[h,x^3]/3 + f[h,x^2]^2/8 + f[h,x^4]/4;
%t A036650 S5[f_,h_,x_] := f[h,x]^5/120 + f[h,x]^3 f[h,x^2]/12 + f[h,x]^2 f[h,x^3]/6 + f[h,x] f[h,x^2]^2/8 + f[h,x] f[h,x^4]/4 + f[h,x^2] f[h,x^3]/6 + f[h,x^5]/5;
%t A036650 T[-1,z_] := 1;  T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S4[T,h-1,z]z, z], n+1];
%t A036650 Sum[Take[CoefficientList[z^(n+1) + S5[T,h-1,z]z - S5[T,h-2,z]z - (T[h-1,z] - T[h-2,z]) (T[h-1,z]-1),z], n+1], {h,1,n/2}] + PadRight[{0,1}, n+1] + Sum[Take[CoefficientList[z^(n+1) + (T[h,z] - T[h-1,z])^2/2 + (T[h,z^2] - T[h-1,z^2])/2, z],n+1], {h,0,n/2}] (* _Robert A. Russell_, Sep 15 2018 *)
%t A036650 b[n_, i_, t_, k_] := b[n,i,t,k] = If[i<1, 0, Sum[Binomial[b[i-1,i-1,
%t A036650   k,k] + j-1, j]* b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
%t A036650 b[0, i_, t_, k_] = 1; m = 4; (* m = maximum children *) n = 40;
%t A036650 gf[x_] = 1 + Sum[b[j-1,j-1,m,m]x^j,{j,1,n}]; (* G.f. for A036718 *)
%t A036650 ci[x_] = SymmetricGroupIndex[m+1, x] /. x[i_] -> gf[x^i];
%t A036650 CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
%t A036650 {x, 0, n}]],x] (* _Robert A. Russell_, Jan 19 2023 *)
%Y A036650 Column k=5 of A144528; A036718 (rooted trees).
%Y A036650 Cf. A036648, A036649.
%K A036650 nonn
%O A036650 0,5
%A A036650 _N. J. A. Sloane_
%E A036650 a(0) changed to 1 by _Andrew Howroyd_, Dec 18 2020