login
Number of n-node connected graphs with one cycle, possibly of length 1 or 2.
5

%I #18 Jun 20 2018 18:46:56

%S 1,2,4,9,20,49,118,300,765,1998,5255,14027,37670,102095,278262,763022,

%T 2101905,5816142,16153148,45017423,125836711,352723949,991143727,

%U 2791422887,7877935985,22275473767,63096075118,179012076933

%N Number of n-node connected graphs with one cycle, possibly of length 1 or 2.

%C a(n) = A000081(n) + A027852(n) + A000226(n) + A000368(n) + ... [_Geoffrey Critzer_, Mar 24 2013]

%H Andrew Howroyd, <a href="/A068051/b068051.txt">Table of n, a(n) for n = 1..200</a>

%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>

%F "DIK" transform of A000081.

%t nn=20;t[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0==Series[t[x]-x Product[1/(1-x^i)^a[i],{i,1,nn}],{x,0,nn}],x];b=Table[a[n],{n,1,nn}]/.sol//Flatten;Map[Total,Drop[Transpose[Table[Take[CoefficientList[CycleIndex[DihedralGroup[n],s]/.Table[s[j]->Table[Sum[b[[i]]x^(i*k),{i,1,nn}],{k,1,nn}][[j]],{j,1,n}],x],nn],{n,1,nn}]],1]] (* _Geoffrey Critzer_, Mar 24 2013 *)

%o (PARI) \\ TreeGf gives gf of A000081

%o TreeGf(N)={my(A=vector(N, j, 1)); for(n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}

%o seq(n)={my(t=TreeGf(n)); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); Vec((sum(d=1, n, eulerphi(d)/d*log(1/(1-g(d)))) + ((1+g(1))^2/(1-g(2))-1)/2)/2)} \\ _Andrew Howroyd_, Jun 20 2018

%Y Cf. A217781.

%K nonn

%O 1,2

%A _Christian G. Bower_, Feb 12 2002