|
%I #59 Feb 02 2024 19:05:18
%S 1,0,0,1,15,222,3670,68820,1456875,34506640,906073524,26154657270,
%T 823808845585,28129686128940,1035350305641990,40871383866109888,
%U 1722832666898627865,77242791668604946560,3670690919234354407000,184312149879830557190940,9751080154504005703189791
%N Number of n-node labeled graphs whose components are unicyclic graphs.
%C Also the number of labeled simple graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. The version without the choice condition is A116508, covering A367863. - _Gus Wiseman_, Jan 25 2024
%D V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999.
%H Alois P. Heinz, <a href="/A137916/b137916.txt">Table of n, a(n) for n = 0..386</a> (terms n = 151..200 from Andrew Howroyd)
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Pseudoforest.html">Pseudoforest</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Pseudoforest">Pseudoforest</a>.
%F a(n) = Sum_{N = 1..n} ((n!/N!) * Sum_{n_1 + n_2 + ... + n_N = n} Product_{i = 1..N} ( A057500(n_i) / n_i! ) ). [V. F. Kolchin p. 31, (1.4.2)] replacing numerator terms n_i^(n_i-2) by A057500(n_i).
%F a(n) = A144228(n,n). - _Alois P. Heinz_, Sep 15 2008
%F E.g.f.: exp(B(T(x))) where B(x) = (log(1/(1-x))-x-x^2/2)/2 and T(x) is the e.g.f. for A000169 (labeled rooted trees). - _Geoffrey Critzer_, Jan 24 2012
%F a(n) ~ 2^(-1/4)*exp(-3/4)*GAMMA(3/4)*n^(n-1/4)/sqrt(Pi) * (1-7*Pi/(12*GAMMA(3/4)^2*sqrt(n))). - _Vaclav Kotesovec_, Aug 16 2013
%F E.g.f.: exp(B(x)) where B(x) is the e.g.f. of A057500. - _Andrew Howroyd_, May 18 2021
%e a(6) = 3670 because A057500(6) = 3660 and two triangles can be labeled in 10 ways.
%e From _Gus Wiseman_, Jan 25 2024: (Start)
%e The a(0) = 1 through a(4) = 15 simple graphs:
%e {} . . {12,13,23} {12,13,14,23}
%e {12,13,14,24}
%e {12,13,14,34}
%e {12,13,23,24}
%e {12,13,23,34}
%e {12,13,24,34}
%e {12,14,23,24}
%e {12,14,23,34}
%e {12,14,24,34}
%e {12,23,24,34}
%e {13,14,23,24}
%e {13,14,23,34}
%e {13,14,24,34}
%e {13,23,24,34}
%e {14,23,24,34}
%e (End)
%p cy:= proc(n) option remember;
%p binomial(n-1, 2)*add((n-3)!/(n-2-t)!*n^(n-2-t), t=1..n-2)
%p end:
%p T:= proc(n,k) option remember; `if`(k=0, 1, `if`(k<0 or n<k, 0,
%p add(binomial(n-1, j)*((j+1)^(j-1)*T(n-j-1, k-j)
%p +cy(j+1)*T(n-j-1, k-j-1)), j=0..k)))
%p end:
%p a:= n-> T(n,n):
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Sep 15 2008
%t nn = 20; t = Sum[n^(n - 1) x^n/n!, {n, 1, nn}]; Drop[Range[0, nn]! CoefficientList[Series[Exp[Log[1/(1 - t)]/2 - t/2 - t^2/4], {x, 0, nn}], x], 1] (* _Geoffrey Critzer_, Jan 24 2012 *)
%t Table[Length[Select[Subsets[Subsets[Range[n],{2}],{n}],Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]],{n,0,5}] (* _Gus Wiseman_, Jan 25 2024 *)
%o (PARI) A057500(p) = (p-1)! * p^p /2 * sum(k = 3,p, 1/(p^k*(p-k)!)); /* _Vladeta Jovovic_, A057500. */
%o F(n,N) = { my(s = 0, K, D, Mc); forpart(P = n, D = Set(P); K = vector(#D);
%o for(i=1, #D, K[i] = #select(x->x == D[i], Vec(P)));
%o Mc = n!/prod(i=1,#D, K[i]!);
%o s += Mc * prod(i = 1, #D, A057500(D[i])^K[i] / ( D[i]!^K[i])) , [3, n], [N, N]); s };
%o a(n)= {my(N); sum(N = 1, n, F(n,N))};
%o (PARI) seq(n)={my(w=lambertw(-x+O(x*x^n))); Vec(serlaplace(exp(-log(1+w)/2 + w/2 - w^2/4)))} \\ _Andrew Howroyd_, May 18 2021
%Y The connected case is A057500.
%Y Row sums of A106239.
%Y The unlabeled version is A137917.
%Y Diagonal of A144228.
%Y The version with loops appears to be A333331, unlabeled A368984.
%Y Column k = 0 of A368924.
%Y The complement is counted by A369143, unlabeled A369201, covering A369144.
%Y A006125 counts simple graphs, unlabeled A000088.
%Y A006129 counts covering graphs, unlabeled A002494.
%Y A054548 counts graphs covering n vertices with k edges, with loops A369199.
%Y A133686 counts choosable simple graphs, covering A367869.
%Y A140637 counts unlabeled non-choosable graphs, covering A369202.
%Y A367867 counts non-choosable graphs, covering A367868.
%Y Cf. A001434, A006649, A053530, A116508, A129271, A134964, A140638, A367862, A367863, A369191.
%K easy,nonn
%O 0,5
%A _Washington Bomfim_, Feb 22 2008
%E a(0)=1 prepended by _Andrew Howroyd_, May 18 2021
|
