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,5

Links

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

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

Example

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)

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 *)

Prog

(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

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.

Sequence in context: A178689 A095983 A059166 * A251588 A126468 A336665

Adjacent sequences: A100740 A100741 A100742 * A100744 A100745 A100746

Keyword

nonn

Author

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

Extensions

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

Status

approved