cp's OEIS Frontend

A133686 Number of labeled n-node graphs with at most one cycle in each connected component.

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