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,5

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

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.

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

Example

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)

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<k, 0,
      add(binomial(n-1, j)*((j+1)^(j-1)*T(n-j-1, k-j)
      +cy(j+1)*T(n-j-1, k-j-1)), j=0..k)))
    end:
a:= 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 *)

Prog

(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

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.

Sequence in context: A027840 A279530 A057500 * A218696 A367863 A297669

Adjacent sequences: A137913 A137914 A137915 * A137917 A137918 A137919

Keyword

easy,nonn

Author

Washington Bomfim, Feb 22 2008

Extensions

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

Status

approved