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

0, 0, 1, 22, 616, 26084, 1885323, 253923163, 66619551326, 34575180977552, 35680008747431929, 73392583275070667841, 301348381377662031986734, 2471956814761854578316988092, 40530184362443276558060719358471, 1328619783326799871747200601484790193

Offset: 0

Author

Gus Wiseman, Jan 20 2024

Keywords

• nonn

Comments

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

Examples

			The a(0) = 0 through a(3) = 22 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{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

The version for a unique choice is A000272, unlabeled A000055.

Without the choice condition we have A006125, unlabeled A000088.

The case without loops is A367868, covering case of A367867.

For exactly n edges we have A368730, covering case of A368596.

The complement is counted by A369140, covering case of A368927.

This is the covering case of A369141.

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

The unlabeled version is A369147, covering case of A369146.

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.

A129271 counts connected choosable graphs, unlabeled A005703.

A133686 counts choosable graphs, covering A367869.

A322661 counts covering loop-graphs, connected A062740, unlabeled A322700.

A367902 counts choosable set-systems, complement A367903.

Cf. A000666, A003465, A006649, A116508, A137916, A333331, A368600, A368924, A368984, A369145, A369194.

Programs

Mathematica

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

Formula

Inverse binomial transform of A369141.

a(n) = A322661(n) - A369140(n). - Andrew Howroyd, Feb 02 2024

Extensions

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