A144527 a(n) = A000055(n) - 2.

0, 1, 4, 9, 21, 45, 104, 233, 549, 1299, 3157, 7739, 19318, 48627, 123865, 317953, 823063, 2144503, 5623754, 14828072, 39299895, 104636888, 279793448, 751065458, 2023443030, 5469566583, 14830871800, 40330829028, 109972410219, 300628862478, 823779631719

Offset: 4

Author

N. J. A. Sloane, Dec 20 2008

Keywords

• nonn

Comments

Number of free trees with n nodes, each node with degree <= n-3. - Robert A. Russell, Jan 25 2023

Links

• Rebecca Neville, Graphs whose vertices are forests with bounded degree, Graph Theory Notes of New York, LIV (2008), 12-21. [Wayback Machine link]

Crossrefs

Cf. A000055, A144528.

Programs

Mathematica

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;
Join[{0, 1}, Table[m = n - 4;
  gf[x_] := 1 + Sum[b[j - 1, j - 1, m, m] x^j, {j, 1, n}];
  ci[x_] := SymmetricGroupIndex[m + 1, x] /. x[i_] -> gf[x^i];
  SeriesCoefficient[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
{x, 0, n}], n], {n,6,35}]] (* Robert A. Russell, Jan 25 2023 *)

Formula

a(n) = A144528(n,n-3). - Robert A. Russell, Jan 25 2023