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

Comments

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

Links

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

Formula

Inverse binomial transform of A369141.

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

Example

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}}

Mathematica

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

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.

Sequence in context: A084271 A092086 A373723 * A218478 A223624 A230836

Adjacent sequences: A369139 A369140 A369141 * A369143 A369144 A369145

Keyword

nonn

Author

Gus Wiseman, Jan 20 2024

Extensions

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

Status

approved