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

Comments

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

Links

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

Formula

Binomial transform of A369142.

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

Example

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

Mathematica

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

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.

Sequence in context: A099365 A215017 A266100 * A266024 A217996 A246906

Adjacent sequences: A369138 A369139 A369140 * A369142 A369143 A369144

Keyword

nonn

Author

Gus Wiseman, Jan 20 2024

Extensions

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

Status

approved