A335342 Number of free trees with exactly n nodes with fewer than three neighbors.

1, 1, 2, 4, 9, 25, 70, 226, 753, 2675, 9785, 37087, 143487, 566952, 2274967, 9257906, 38113299, 158535204, 665364565, 2814924441, 11993967450, 51433198599, 221839745468, 961884808879, 4190783204515, 18339291329225

Offset: 1

Author

Robert A. Russell, Jun 02 2020

Keywords

• nonn
• easy

Comments

Generates and uses values from A108521, rooted trees with exactly n generators, a generator being a leaf or node with just one child.

Examples

			For n=4, we have 1) a node with four neighbors, 2) two adjacent nodes with three neighbors each, 3) two adjacent nodes with two neighbors each, and 4) two adjacent nodes, one having two neighbors and the other three neighbors.
		

Links

• Robert A. Russell, Table of n, a(n) for n = 1..60
• R. A. Russell, How many trees have n nodes with fewer than three neighbors?, MathOverflow, June 2020.

Crossrefs

Cf. A108521 (rooted trees).

Programs

Mathematica

a[1] = 1; a[n_] := a[n] = 1+a[n-1] + Total[Product[Binomial[a[i]-1+Count[#,i], Count[#,i]], {i, DeleteCases[DeleteDuplicates[#], 1]}] & /@ IntegerPartitions[n,{2, n-1}]]; (* A108521 *)
b[1] = 1; b[n_] := b[n] = If[n > 2, 1, 0] + If[EvenQ[n], a[n/2] (a[n/2] + 1)/2, a[(n-1)/2] (a[(n-1)/2]+1)/2] + If[n > 3, Total[If[Max[#] <= If[EvenQ[n], n/2-1, (n-1)/2], Product[Binomial[a[i] - 1 + Count[#, i], Count[#, i]], {i, DeleteCases[DeleteDuplicates[#], 1]}], 0] & /@ IntegerPartitions[n, {3, n-1}]], 0];
Table[b[n], {n, 40}]
(* a[n] = A108521[n]; d[n] are coefficients of A^2(x) in g.f. *)
a[0] = 0; a[1] = 1; a[n_] := a[n] = a[n-1] + (DivisorSum[n, a[#] # &, #
				

PARI

\\ here S is A108521 as vector.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
S(n)={my(v=[1]); for(n=2, n, v=concat(v, v[#v] + EulerT(concat(v, [0]))[n])); v}
seq(n)={my(p=x*Ser(S(n))); Vec(p + (x/2-1)*p^2 + (x/2)*subst(p, x, x^2))} \\ Andrew Howroyd, Jun 06 2020

Formula

G.f.: A(x) + (x/2-1)*A^2(x) + (x/2)*A(x^2), where A(x) is the g.f. for A108521.