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

1, 0, 0, 1, 10, 253, 12068, 1052793, 169505868, 51046350021, 29184353055900, 32122563615242615, 68867440268165982320, 290155715157676330952559, 2417761590648159731258579164, 40013923822242935823157820555477, 1318910080336893719646370269435043184

Offset: 0

Author

Goran Kilibarda, Zoran Maksimovic, Vladeta Jovovic, Jan 03 2005

Keywords

• nonn

Examples

			From _Gus Wiseman_, Aug 18 2019: (Start)
The a(4) = 10 edge-sets:
  {12,13,24,34}
  {12,14,23,34}
  {13,14,23,24}
  {12,13,14,23,24}
  {12,13,14,23,34}
  {12,13,14,24,34}
  {12,13,23,24,34}
  {12,14,23,24,34}
  {13,14,23,24,34}
  {12,13,14,23,24,34}
(End)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50

Crossrefs

Graphs without isolated nodes are A006129.

The connected case is A059166.

Graphs without endpoints are A059167.

Labeled graphs with endpoints are A245797.

The unlabeled version is A261919.

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

Cf. A095983, A322395.

Programs

Mathematica

m = 13;
egf = Exp[-x + x^2/2]*Sum[2^(n (n-1)/2)*(x/Exp[x])^n/n!, {n, 0, m+1}];
s = egf + O[x]^(m+1);
a[n_] := n!*SeriesCoefficient[s, n];
Table[a[n], {n, 0, m}] (* Jean-François Alcover, Feb 23 2019 *)
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 *)

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

Formula

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

Exponential transform of A059166. - Gus Wiseman, Aug 18 2019

Inverse binomial transform of A059167. - Gus Wiseman, Sep 02 2019

Extensions

Terms a(14) and beyond from Andrew Howroyd, Sep 04 2019