login
a(n) is the number of unlabeled unrooted trees (as in A000055) on n nodes with one designated node (exclusive) or one designated edge.
1

%I #60 Feb 17 2024 13:39:58

%S 0,1,2,3,7,15,36,85,211,525,1341,3449,9001,23671,62835,167881,451557,

%T 1221065,3318737,9059397,24830110,68299159,188488448,521737636,

%U 1448154837,4029712400,11239492056,31416403198,87990722479,246903542031,694022911203,1954012196966

%N a(n) is the number of unlabeled unrooted trees (as in A000055) on n nodes with one designated node (exclusive) or one designated edge.

%H Alois P. Heinz, <a href="/A328779/b328779.txt">Table of n, a(n) for n = 0..2135</a>

%H Mathematics Stack Exchange <a href="https://math.stackexchange.com/questions/1915320/counting-free-trees-from-rooted-trees">Counting free trees from rooted trees</a>.

%F O.g.f.: R(x) + R(x)^2/2 + R(x^2)/2 where R(x) is the o.g.f. for A000081.

%p b:= proc(n) option remember; `if`(n<2, n, (add(b(n-j)*add(

%p d*b(d), d=numtheory[divisors](j)), j=1..n-1))/(n-1))

%p end:

%p a:= n-> b(n)+add(b(j)*b(n-j), j=0..n)/2+`if`(n::even, b(n/2)/2, 0):

%p seq(a(n), n=0..31); # _Alois P. Heinz_, Feb 17 2024

%t nn = 25; f[x_] := Sum[a[n] x^n, {n, 0, nn}]; sol = SolveAlways[

%t 0 == Series[f[x] - x Product[1/(1 - x^i)^a[i], {i, 1, nn}], {x, 0, nn}], x];

%t r[x_] := Sum[a[n] x^n, {n, 0, nn}] /. sol; CoefficientList[Series[r[x] + r[x]^2/2 + r[x^2]/2, {x, 0, nn}], x]

%Y Cf. A000055, A000081.

%K nonn

%O 0,3

%A _Geoffrey Critzer_, Jul 06 2020