cp's OEIS Frontend

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

%I A335342 #25 Jun 10 2020 17:46:48
%S A335342 1,1,2,4,9,25,70,226,753,2675,9785,37087,143487,566952,2274967,
%T A335342 9257906,38113299,158535204,665364565,2814924441,11993967450,
%U A335342 51433198599,221839745468,961884808879,4190783204515,18339291329225
%N A335342 Number of free trees with exactly n nodes with fewer than three neighbors.
%C A335342 Generates and uses values from A108521, rooted trees with exactly n generators, a generator being a leaf or node with just one child.
%H A335342 Robert A. Russell, <a href="/A335342/b335342.txt">Table of n, a(n) for n = 1..60</a>
%H A335342 R. A. Russell, <a href="https://mathoverflow.net/questions/361860/how-many-trees-have-n-nodes-with-fewer-than-three-neighbors">How many trees have n nodes with fewer than three neighbors?</a>, MathOverflow, June 2020.
%F A335342 G.f.: A(x) + (x/2-1)*A^2(x) + (x/2)*A(x^2), where A(x) is the g.f. for A108521.
%e A335342 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.
%t A335342 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 *)
%t A335342 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];
%t A335342 Table[b[n], {n, 40}]
%t A335342 (* a[n] = A108521[n]; d[n] are coefficients of A^2(x) in g.f. *)
%t A335342 a[0] = 0; a[1] = 1; a[n_] := a[n] = a[n-1] + (DivisorSum[n, a[#] # &, #<n &] + Sum[c[k] b[n-k], {k,n-1}])/n; b[n_] := b[n] = (c[n] + Sum[c[k] b[n-k], {k,n-1}])/n; c[n_] := c[n] = DivisorSum[n, a[#] # &]; d[n_] := d[n] = Sum[2 a[k] a[n-k], {k,Floor[(n-1)/2]}] + If[EvenQ[n], a[n/2]^2, 0]; Table[a[n] - d[n] + (d[n-1] + If[OddQ[n], a[(n-1)/2], 0])/2, {n,40}]
%o A335342 (PARI) \\ here S is A108521 as vector.
%o A335342 EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
%o A335342 S(n)={my(v=[1]); for(n=2, n, v=concat(v, v[#v] + EulerT(concat(v, [0]))[n])); v}
%o A335342 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
%Y A335342 Cf. A108521 (rooted trees).
%K A335342 nonn,easy
%O A335342 1,3
%A A335342 _Robert A. Russell_, Jun 02 2020