|
%I M1151 #57 Feb 21 2024 22:49:02
%S 1,1,1,2,4,8,19,44,112,287,763,2041,5577,15300,42419,118122,330785,
%T 929469,2621272,7411706,21010378,59682057,169859257,484234165,
%U 1382567947,3952860475,11315775161,32430737380,93044797486,267211342954,768096496093,2209772802169
%N Number of n-node connected graphs with at most one cycle.
%C a(n) is the number of pseudotrees on n nodes. - _Eric W. Weisstein_, Jun 11 2012
%C Also unlabeled connected graphs covering n vertices with at most n edges. For this definition we have a(1) = 0 and possibly a(0) = 0. - _Gus Wiseman_, Feb 20 2024
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Washington Bomfim, <a href="/A005703/b005703.txt">Table of n, a(n) for n = 0..500</a>
%H R. K. Guy, <a href="/A000123/a000123_1.pdf">Letters to N. J. A. Sloane and J. W. Moon, 1988</a>
%H Richard J. Mathar, <a href="https://arxiv.org/abs/1808.06264">Counting Connected Graphs without Overlapping Cycles</a>, arXiv:1808.06264 [math.CO], 2018.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Pseudotree.html">Pseudotree</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Pseudoforest">Pseudoforest</a>
%F a(n) = A000055(n) + A001429(n).
%e From _Gus Wiseman_, Feb 20 2024: (Start)
%e Representatives of the a(0) = 1 through a(5) = 8 graphs:
%e {} . {12} {12,13} {12,13,14} {12,13,14,15}
%e {12,13,23} {12,13,24} {12,13,14,25}
%e {12,13,14,23} {12,13,24,35}
%e {12,13,24,34} {12,13,14,15,23}
%e {12,13,14,23,25}
%e {12,13,14,23,45}
%e {12,13,14,25,35}
%e {12,13,24,35,45}
%e (End)
%t Needs["Combinatorica`"]; nn = 20; t[x_] := Sum[a[n] x^n, {n, 1, nn}];
%t a[0] = 0;
%t b = Drop[Flatten[
%t sol = SolveAlways[
%t 0 == Series[
%t t[x] - x Product[1/(1 - x^i)^a[i], {i, 1, nn}], {x, 0, nn}],
%t x]; Table[a[n], {n, 0, nn}] /. sol], 1];
%t r[x_] := Sum[b[[n]] x^n, {n, 1, nn}]; c =
%t Drop[Table[
%t CoefficientList[
%t Series[CycleIndex[DihedralGroup[n], s] /.
%t Table[s[i] -> r[x^i], {i, 1, n}], {x, 0, nn}], x], {n, 3,
%t nn}] // Total, 1];
%t d[x_] := Sum[c[[n]] x^n, {n, 1, nn}]; CoefficientList[
%t Series[r[x] - (r[x]^2 - r[x^2])/2 + d[x] + 1, {x, 0, nn}], x] (* _Geoffrey Critzer_, Nov 17 2014 *)
%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(1 + g(1) + (g(2) - g(1)^2)/2 + sum(k=3, n, sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/k + if(k%2, g(1)*g(2)^(k\2), (g(1)^2+g(2))*g(2)^(k/2-1)/2))/2)}; \\ _Andrew Howroyd_ and _Washington Bomfim_, May 15 2021
%Y Cf. A000055, A000081, A001429 (labeled A057500), A134964 (number of pseudoforests, labeled A133686).
%Y The labeled version is A129271.
%Y The connected complement is A140636, labeled A140638.
%Y Non-connected: A368834 (labeled A367869) or A370316 (labeled A369191).
%Y A001187 counts connected graphs, unlabeled A001349.
%Y A006125 counts simple graphs, unlabeled A000088.
%Y A006129 counts covering graphs, unlabeled A002494.
%Y A062734 counts connected graphs by number of edges.
%Y Cf. A000272, A006649, A116508, A140637, A143543, A367862, A367863, A368951, A369197, A370317, A370318.
%K nonn,easy,nice
%O 0,4
%A _N. J. A. Sloane_, _R. K. Guy_
%E More terms from _Vladeta Jovovic_, Apr 19 2000 and from _Michael Somos_, Apr 26 2000
%E a(27) corrected and a(28) and a(29) computed by _Washington Bomfim_, May 14 2008
|
