A137916 Number of n-node labeled graphs whose components are unicyclic graphs.

1, 0, 0, 1, 15, 222, 3670, 68820, 1456875, 34506640, 906073524, 26154657270, 823808845585, 28129686128940, 1035350305641990, 40871383866109888, 1722832666898627865, 77242791668604946560, 3670690919234354407000, 184312149879830557190940, 9751080154504005703189791

Offset: 0

Author

Washington Bomfim, Feb 22 2008

Keywords

• easy
• nonn

Comments

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

Examples

			a(6) = 3670 because A057500(6) = 3660 and two triangles can be labeled in 10 ways.
From _Gus Wiseman_, Jan 25 2024: (Start)
The a(0) = 1 through a(4) = 15 simple graphs:
  {}  .  .  {12,13,23}  {12,13,14,23}
                        {12,13,14,24}
                        {12,13,14,34}
                        {12,13,23,24}
                        {12,13,23,34}
                        {12,13,24,34}
                        {12,14,23,24}
                        {12,14,23,34}
                        {12,14,24,34}
                        {12,23,24,34}
                        {13,14,23,24}
                        {13,14,23,34}
                        {13,14,24,34}
                        {13,23,24,34}
                        {14,23,24,34}
(End)
		

References

• V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..386 (terms n = 151..200 from Andrew Howroyd)
• Eric Weisstein's World of Mathematics, Pseudoforest.
• Wikipedia, Pseudoforest.

Crossrefs

The connected case is A057500.

Row sums of A106239.

The unlabeled version is A137917.

Diagonal of A144228.

The version with loops appears to be A333331, unlabeled A368984.

Column k = 0 of A368924.

The complement is counted by A369143, unlabeled A369201, covering A369144.

A006125 counts simple graphs, unlabeled A000088.

A006129 counts covering graphs, unlabeled A002494.

A054548 counts graphs covering n vertices with k edges, with loops A369199.

A133686 counts choosable simple graphs, covering A367869.

A140637 counts unlabeled non-choosable graphs, covering A369202.

A367867 counts non-choosable graphs, covering A367868.

Cf. A001434, A006649, A053530, A116508, A129271, A134964, A140638, A367862, A367863, A369191.

Programs

Maple

cy:= proc(n) option remember;
       binomial(n-1, 2)*add((n-3)!/(n-2-t)!*n^(n-2-t), t=1..n-2)
     end:
T:= proc(n,k) option remember; `if`(k=0, 1, `if`(k<0 or n T(n,n):
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 15 2008

Mathematica

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 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}],{n}],Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]],{n,0,5}] (* Gus Wiseman, Jan 25 2024 *)

PARI

A057500(p) = (p-1)! * p^p /2 * sum(k = 3,p, 1/(p^k*(p-k)!)); /* Vladeta Jovovic, A057500. */
F(n,N) = { my(s = 0, K, D, Mc); forpart(P = n, D = Set(P); K = vector(#D);
for(i=1, #D, K[i] = #select(x->x == D[i], Vec(P)));
Mc = n!/prod(i=1,#D, K[i]!);
s += Mc * prod(i = 1, #D, A057500(D[i])^K[i] / ( D[i]!^K[i])) , [3, n], [N, N]); s };
a(n)= {my(N); sum(N = 1, n, F(n,N))};

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

Formula

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).

a(n) = A144228(n,n). - Alois P. Heinz, Sep 15 2008

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

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

E.g.f.: exp(B(x)) where B(x) is the e.g.f. of A057500. - Andrew Howroyd, May 18 2021

Extensions

a(0)=1 prepended by Andrew Howroyd, May 18 2021