OFFSET
0,3
COMMENTS
The total number of those graphs of order 5 is 608. The number of forests of trees on n labeled nodes of order 5 is 291, so the majority of the graphs of that kind have one or more unicycles.
Also the number of labeled graphs with n vertices satisfying a strict version of the axiom of choice. The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once. The connected case is A129271, complement A140638. The unlabeled version is A134964. - Gus Wiseman, Dec 22 2023
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..386
Wikipedia, Pseudoforest
FORMULA
a(0) = 1; for n >=1, a(n) = Sum of n!prod_{j=1}^n\{ frac{ A129271(j)^{c_j} } { j!^{c_j}c_j! } } over all the partitions of n, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0.
a(n) = Sum_{k=0..n} A144228(n,k). - Alois P. Heinz, Sep 15 2008
E.g.f.: sqrt(-LambertW(-x)/(x*(1+LambertW(-x))))*exp(-3/4 * LambertW(-x)^2). - Vladeta Jovovic, Sep 16 2008
E.g.f.: A(x)*B(x) where A(x) is the e.g.f. for A137916 and B(x) is the e.g.f. for A001858. - Geoffrey Critzer, Mar 23 2013
a(n) ~ 2^(-1/4) * Gamma(3/4) * exp(-1/4) * n^(n-1/4) / sqrt(Pi) * (1-7*Pi/(12*Gamma(3/4)^2*sqrt(n))). - Vaclav Kotesovec, Oct 08 2013
E.g.f.: exp(B(x) - 1) where B(x) is the e.g.f. of A129271. - Andrew Howroyd, Dec 30 2023
EXAMPLE
Below we see the 7 partitions of n=5 in the form c_1 + 2c_2 + ... + nc_n followed by the corresponding number of graphs. We consider the values of A129271(j) given by the table
j|1|2|3| 4| 5|
----+-+-+-+--+---+
a(j)|1|1|4|31|347|
1*5 -> 5!1^5 / (1!^5 * 5!) = 1
2*1 + 1*3 -> 5!1^1 * 1^3 / (2!^1 * 1! * 1!^3 * 3!) = 10
2*2 + 1*1 -> 5!1^2 * 1^1 / (2!^2 * 2! * 1!^1 * 1!) = 15
3*1 + 1*2 -> 5!4^1 * 1^2 / (3!^1 * 1! * 1!^2 * 2!) = 40
3*1 + 2*1 -> 5!4^1 * 1^1 / (3!^1 * 1! * 2!^1 * 1!) = 40
4*1 + 1*1 -> 5!31^1 * 1^1 / (4!^1 * 1! * 1!^1 * 1!) = 155
5*1 -> 5!347^1 / (5!^1 * 1!) = 347
Total 608
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 then 1
elif k<0 or n<k then 0
else 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)
fi
end:
a:= n-> add(T(n, k), k=0..n):
seq(a(n), n=0..20); # Alois P. Heinz, Sep 15 2008
MATHEMATICA
nn=20; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; Range[0, nn]!CoefficientList[ Series[ Exp[t/2-3t^2/4]/(1-t)^(1/2), {x, 0, nn}], x] (* Geoffrey Critzer, Sep 05 2012 *)
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Select[Tuples[#], UnsameQ@@#&]!={}&]], {n, 0, 5}] (* Gus Wiseman, Dec 22 2023 *)
PROG
(PARI) x='x+O('x^50); Vec(serlaplace(sqrt(-lambertw(-x)/(x*(1+ lambertw(-x))))*exp(-(3/4)*lambertw(-x)^2))) \\ G. C. Greubel, Nov 16 2017
CROSSREFS
Row sums of triangle A144228. - Alois P. Heinz, Sep 15 2008
Cf. A137352. - Vladeta Jovovic, Sep 16 2008
The unlabeled version is A134964.
A143543 counts graphs by number of connected components.
KEYWORD
easy,nonn
AUTHOR
Washington Bomfim, May 12 2008
EXTENSIONS
Corrected and extended by Alois P. Heinz and Vladeta Jovovic, Sep 15 2008
STATUS
approved