login
Number of centered 6-valent trees with n nodes.
2

%I #19 Dec 26 2020 11:09:30

%S 0,1,0,1,1,2,3,7,11,26,52,120,266,640,1509,3702,9090,22781,57452,

%T 146783,377357,978342,2550611,6690242,17633855,46705333,124227015,

%U 331757697,889207207,2391478247,6451880415,17457214729,47363110968

%N Number of centered 6-valent trees with n nodes.

%H 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 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F a(n) = A036653(n) - A036652(n).

%t n = 20; (* algorithm from Rains and Sloane *)

%t 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 S6[f_,h_,x_] := f[h,x]^6/720 + f[h,x]^4 f[h,x^2]/48 + f[h,x]^3 f[h,x^3]/18 + f[h,x]^2 f[h,x^2]^2/16 + f[h,x]^2 f[h,x^4]/8 + f[h,x] f[h,x^2] f[h,x^3]/6 + f[h,x] f[h,x^5]/5 + f[h,x^2]^3/48 + f[h,x^2] f[h,x^4]/8 + f[h,x^3]^2/18 + f[h,x^6]/6;

%t T[-1,z_] := 1; T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S5[T,h-1,z]z, z], n+1];

%t Sum[Take[CoefficientList[z^(n+1) + S6[T,h-1,z]z - S6[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] (* _Robert A. Russell_, Sep 15 2018 *)

%Y Cf. A036652, A036653.

%K nonn

%O 0,6

%A _N. J. A. Sloane_