A036650 Number of 5-valent trees with n nodes.

1, 1, 1, 1, 2, 3, 6, 10, 21, 42, 94, 204, 473, 1098, 2633, 6353, 15641, 38789, 97416, 246410, 628726, 1614292, 4171955, 10839366, 28308678, 74266477, 195667533, 517504253, 1373640355, 3658205088, 9772510063, 26181295237, 70330621171

Offset

0,5

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.

E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees)., J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.

Index entries for sequences related to trees

Formula

a(n) = A036648(n) + A036649(n) for n > 0.

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

Mathematica

n = 30; (* algorithm from Rains and Sloane *)
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;
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[-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];
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 *)
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]}]];
b[0, i_, t_, k_] = 1; m = 4; (* m = maximum children *) n = 40;
gf[x_] = 1 + Sum[b[j-1, j-1, m, m]x^j, {j, 1, n}]; (* G.f. for A036718 *)
ci[x_] = SymmetricGroupIndex[m+1, x] /. x[i_] -> gf[x^i];
CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
{x, 0, n}]], x] (* Robert A. Russell, Jan 19 2023 *)

Crossrefs

Column k=5 of A144528; A036718 (rooted trees).

Cf. A036648, A036649.

Sequence in context: A265582 A242563 A240513 * A049889 A014270 A127076

Adjacent sequences: A036647 A036648 A036649 * A036651 A036652 A036653

Keyword

nonn

Author

N. J. A. Sloane

Extensions

a(0) changed to 1 by Andrew Howroyd, Dec 18 2020

Status

approved