A368927 Number of labeled loop-graphs covering a subset of {1..n} such that it is possible to choose a different vertex from each edge.

1, 2, 7, 39, 314, 3374, 45630, 744917, 14245978, 312182262, 7708544246, 211688132465, 6397720048692, 210975024924386, 7537162523676076, 289952739051570639, 11949100971787370300, 525142845422124145682, 24515591201199758681892, 1211486045654016217202663

Offset: 0

Author

Gus Wiseman, Jan 15 2024

Keywords

• nonn

Comments

These are loop-graphs where every connected component has a number of edges less than or equal to the number of vertices. Also loop-graphs with at most one cycle (unicyclic) in each connected component.

Examples

			The a(0) = 1 through a(2) = 7 loop-graphs (loops shown as singletons):
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1,2}}
             {{1},{2}}
             {{1},{1,2}}
             {{2},{1,2}}
		

Links

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

Crossrefs

Without the choice condition we have A006125.

The case of a unique choice is A088957, unlabeled A087803.

The case without loops is A133686, complement A367867, covering A367869.

For exactly n edges and no loops we have A137916, unlabeled A137917.

For exactly n edges we have A333331 (maybe), complement A368596.

For edges of any positive size we have A367902, complement A367903.

The covering case is A369140, complement A369142.

The complement is counted by A369141.

The complement for n edges and no loops is A369143, covering A369144.

The unlabeled version is A369145, complement A369146.

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

A006129 counts covering graphs, unlabeled A002494.

A322661 counts labeled covering loop-graphs, connected A062740.

Cf. A000169, A000272, A000666, A014068, A057500, A116508, A367863, A368601, A368924, A368984, A369200.

Programs

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n],{1,2}]], Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]],{n,0,5}]

PARI

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(exp(3*t/2 - 3*t^2/4)/sqrt(1-t) ))} \\ Andrew Howroyd, Feb 02 2024

Formula

Binomial transform of A369140.

Exponential transform of A369197 with A369197(1) = 2.

E.g.f.: exp(3*T(x)/2 - 3*T(x)^2/4)/sqrt(1-T(x)), where T(x) is the e.g.f. of A000169. - Andrew Howroyd, Feb 02 2024

Extensions

a(7) onwards from Andrew Howroyd, Feb 02 2024