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
KEYWORD
easy,nonn
AUTHOR
Washington Bomfim, Feb 22 2008
EXTENSIONS
a(0)=1 prepended by Andrew Howroyd, May 18 2021
STATUS
approved