login
Number of labeled n-vertex graphs without vertices of degree <=1.
14

%I #20 Sep 04 2019 21:44:27

%S 1,0,0,1,10,253,12068,1052793,169505868,51046350021,29184353055900,

%T 32122563615242615,68867440268165982320,290155715157676330952559,

%U 2417761590648159731258579164,40013923822242935823157820555477,1318910080336893719646370269435043184

%N Number of labeled n-vertex graphs without vertices of degree <=1.

%H Andrew Howroyd, <a href="/A100743/b100743.txt">Table of n, a(n) for n = 0..50</a>

%F E.g.f.: exp(-x+x^2/2)*(Sum_{n>=0} 2^(n*(n-1)/2)*(x/exp(x))^n/n!). - _Vladeta Jovovic_, Jan 26 2006

%F Exponential transform of A059166. - _Gus Wiseman_, Aug 18 2019

%F Inverse binomial transform of A059167. - _Gus Wiseman_, Sep 02 2019

%e From _Gus Wiseman_, Aug 18 2019: (Start)

%e The a(4) = 10 edge-sets:

%e {12,13,24,34}

%e {12,14,23,34}

%e {13,14,23,24}

%e {12,13,14,23,24}

%e {12,13,14,23,34}

%e {12,13,14,24,34}

%e {12,13,23,24,34}

%e {12,14,23,24,34}

%e {13,14,23,24,34}

%e {12,13,14,23,24,34}

%e (End)

%t m = 13;

%t egf = Exp[-x + x^2/2]*Sum[2^(n (n-1)/2)*(x/Exp[x])^n/n!, {n, 0, m+1}];

%t s = egf + O[x]^(m+1);

%t a[n_] := n!*SeriesCoefficient[s, n];

%t Table[a[n], {n, 0, m}] (* _Jean-François Alcover_, Feb 23 2019 *)

%t Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Min@@Length/@Split[Sort[Join@@#]]>1&]],{n,0,4}] (* _Gus Wiseman_, Aug 18 2019 *)

%o (PARI) seq(n)={Vec(serlaplace(exp(-x + x^2/2 + O(x*x^n))*sum(k=0, n, 2^(k*(k-1)/2)*(x/exp(x + O(x^n)))^k/k!)))} \\ _Andrew Howroyd_, Sep 04 2019

%Y Graphs without isolated nodes are A006129.

%Y The connected case is A059166.

%Y Graphs without endpoints are A059167.

%Y Labeled graphs with endpoints are A245797.

%Y The unlabeled version is A261919.

%Y Cf. A095983, A136284, A322395, A327079, A327107, A327227, A327229, A327230.

%Y Cf. A095983, A322395.

%K nonn

%O 0,5

%A Goran Kilibarda, Zoran Maksimovic, _Vladeta Jovovic_, Jan 03 2005

%E Terms a(14) and beyond from _Andrew Howroyd_, Sep 04 2019