A369141 Number of labeled loop-graphs covering a subset of {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

0, 0, 1, 25, 710, 29394, 2051522, 267690539, 68705230758, 35184059906570, 36028789310419722, 73786976083150073999, 302231454897259573627852, 2475880078570549574773324062, 40564819207303333310731978895956, 1329227995784915872613854321228773937

Offset: 0

Author

Gus Wiseman, Jan 20 2024

Keywords

• nonn

Comments

Also labeled loop-graphs having at least one connected component containing more edges than vertices.

Examples

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

Links

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

Crossrefs

Without the choice condition we have A006125, unlabeled A000088.

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

The case without loops is A367867, covering A367868.

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

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

The complement is counted by A368927, covering A369140.

The covering case is A369142.

For n edges and no loops we have A369143, covering A369144.

The unlabeled version is A369146 (covering A369147), complement A369145.

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

A006129 counts covering graphs, unlabeled A002494.

A054548 counts graphs covering n vertices with k edges, with loops A369199.

A133686 counts choosable graphs, covering A367869.

A322661 counts labeled covering loop-graphs, unlabeled A322700.

Cf. A000272, A000666, A006649, A062740, A116508, A137916, A368924, A368984, A369194.

Programs

Mathematica

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

Formula

Binomial transform of A369142.

a(n) = A006125(n + 1) - A368927(n). - Andrew Howroyd, Feb 02 2024

Extensions

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