A370165 Number of labeled loop-graphs covering n vertices without a non-loop edge with loops at both ends.

1, 1, 4, 29, 400, 10289, 496548, 45455677, 7983420736, 2716094133313, 1803251169342820, 2348787270663723581, 6024912118926389490448, 30516957491540079828757553, 305811332460677494410532494660, 6071677788061208810793717466942237

Offset

0,3

Comments

Number of ways to choose a stable vertex set of a simple graph with n vertices.

Links

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

Formula

Inverse binomial transform of A079491.

E.g.f.: Sum_{k >= 0} exp((2^k-1)*x)*2^(k*(k-1)/2)*x^k/k!. - Andrew Howroyd, Feb 20 2024

Example

The a(3) = 29 loop-graphs (loops shown as singletons):
  {1,23}   {1,2,3}     {1,2,13,23}
  {2,13}   {1,2,13}    {1,3,12,23}
  {3,12}   {1,2,23}    {2,3,12,13}
  {12,13}  {1,3,12}    {1,12,13,23}
  {12,23}  {1,3,23}    {2,12,13,23}
  {13,23}  {2,3,12}    {3,12,13,23}
           {2,3,13}
           {1,12,13}
           {1,12,23}
           {1,13,23}
           {2,12,13}
           {2,12,23}
           {2,13,23}
           {3,12,13}
           {3,12,23}
           {3,13,23}
           {12,13,23}

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n], {1, 2}]], Union@@#==Range[n]&&!MatchQ[#, {___, {x_}, ___, {y_}, ___, {x_, y_}, ___}]&]], {n, 0, 5}]

Prog

(PARI) seq(n)={Vec(serlaplace(sum(k=0, n, exp((2^k-1)*x + O(x*x^n))*2^(k*(k-1)/2)*x^k/k!)))} \\ Andrew Howroyd, Feb 20 2024

Crossrefs

Without loops we have A006129, connected A001187.

The non-covering version is A079491.

The unlabeled version is A370166, non-covering A339832.

A000085, A100861, A111924 count set partitions into singletons or pairs.

A000666 counts unlabeled loop-graphs, covering A322700.

A006125 counts labeled loop-graphs (shifted left), covering A322661.

Cf. A048291, A062740, A116539, A320461, A322635.

Sequence in context: A135485 A210526 A221079 * A162287 A324227 A277357

Adjacent sequences: A370162 A370163 A370164 * A370166 A370167 A370168

Keyword

nonn

Author

Gus Wiseman, Feb 12 2024

Status

approved