|
%I #44 Dec 30 2023 17:12:10
%S 1,1,2,8,57,608,8524,145800,2918123,66617234,1704913434,48300128696,
%T 1499864341015,50648006463048,1847622972848648,72406232075624192,
%U 3033607843748296089,135313823447621913500,6402077421524339766058,320237988317922139148736
%N Number of labeled n-node graphs with at most one cycle in each connected component.
%C 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.
%C 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
%H Alois P. Heinz, <a href="/A133686/b133686.txt">Table of n, a(n) for n = 0..386</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Pseudoforest">Pseudoforest</a>
%F 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.
%F a(n) = Sum_{k=0..n} A144228(n,k). - _Alois P. Heinz_, Sep 15 2008
%F E.g.f.: sqrt(-LambertW(-x)/(x*(1+LambertW(-x))))*exp(-3/4 * LambertW(-x)^2). - _Vladeta Jovovic_, Sep 16 2008
%F 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
%F 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
%F E.g.f.: exp(B(x) - 1) where B(x) is the e.g.f. of A129271. - _Andrew Howroyd_, Dec 30 2023
%e 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
%e j|1|2|3| 4| 5|
%e ----+-+-+-+--+---+
%e a(j)|1|1|4|31|347|
%e 1*5 -> 5!1^5 / (1!^5 * 5!) = 1
%e 2*1 + 1*3 -> 5!1^1 * 1^3 / (2!^1 * 1! * 1!^3 * 3!) = 10
%e 2*2 + 1*1 -> 5!1^2 * 1^1 / (2!^2 * 2! * 1!^1 * 1!) = 15
%e 3*1 + 1*2 -> 5!4^1 * 1^2 / (3!^1 * 1! * 1!^2 * 2!) = 40
%e 3*1 + 2*1 -> 5!4^1 * 1^1 / (3!^1 * 1! * 2!^1 * 1!) = 40
%e 4*1 + 1*1 -> 5!31^1 * 1^1 / (4!^1 * 1! * 1!^1 * 1!) = 155
%e 5*1 -> 5!347^1 / (5!^1 * 1!) = 347
%e Total 608
%p cy:= proc(n) option remember; binomial(n-1, 2)*
%p add((n-3)!/(n-2-t)! *n^(n-2-t), t=1..n-2)
%p end:
%p T:= proc(n,k) option remember;
%p if k=0 then 1
%p elif k<0 or n<k then 0
%p else 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 fi
%p end:
%p a:= n-> add(T(n,k), k=0..n):
%p seq(a(n), n=0..20); # _Alois P. Heinz_, Sep 15 2008
%t 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 *)
%t Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Select[Tuples[#], UnsameQ@@#&]!={}&]],{n,0,5}] (* _Gus Wiseman_, Dec 22 2023 *)
%o (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
%Y Cf. A129137, A005703, A000272, A057500, A137916, A001858.
%Y Row sums of triangle A144228. - _Alois P. Heinz_, Sep 15 2008
%Y Cf. A137352. - _Vladeta Jovovic_, Sep 16 2008
%Y The unlabeled version is A134964.
%Y The complement is counted by A367867, covering A367868, connected A140638.
%Y The covering case is A367869, connected A129271.
%Y For set-systems we have A367902, ranks A367906.
%Y The complement for set-systems is A367903, ranks A367907.
%Y A006125 counts graphs, A000088 unlabeled.
%Y A006129 counts covering graphs, A002494 unlabeled.
%Y A143543 counts graphs by number of connected components.
%Y Cf. A001187, A058891, A116508, A355740, A367769, A367770, A367863, A367901.
%K easy,nonn
%O 0,3
%A _Washington Bomfim_, May 12 2008
%E Corrected and extended by _Alois P. Heinz_ and _Vladeta Jovovic_, Sep 15 2008
| 