

A335342


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


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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


LINKS



FORMULA

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


EXAMPLE

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.


MATHEMATICA

a[1] = 1; a[n_] := a[n] = 1+a[n1] + Total[Product[Binomial[a[i]1+Count[#, i], Count[#, i]], {i, DeleteCases[DeleteDuplicates[#], 1]}] & /@ IntegerPartitions[n, {2, n1}]]; (* 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[(n1)/2] (a[(n1)/2]+1)/2] + If[n > 3, Total[If[Max[#] <= If[EvenQ[n], n/21, (n1)/2], Product[Binomial[a[i]  1 + Count[#, i], Count[#, i]], {i, DeleteCases[DeleteDuplicates[#], 1]}], 0] & /@ IntegerPartitions[n, {3, n1}]], 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[n1] + (DivisorSum[n, a[#] # &, #<n &] + Sum[c[k] b[nk], {k, n1}])/n; b[n_] := b[n] = (c[n] + Sum[c[k] b[nk], {k, n1}])/n; c[n_] := c[n] = DivisorSum[n, a[#] # &]; d[n_] := d[n] = Sum[2 a[k] a[nk], {k, Floor[(n1)/2]}] + If[EvenQ[n], a[n/2]^2, 0]; Table[a[n]  d[n] + (d[n1] + If[OddQ[n], a[(n1)/2], 0])/2, {n, 40}]


PROG

(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/21)*p^2 + (x/2)*subst(p, x, x^2))} \\ Andrew Howroyd, Jun 06 2020


CROSSREFS



KEYWORD

nonn,easy


AUTHOR



STATUS

approved



