A369147 Number of unlabeled loop-graphs covering n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).

0, 0, 1, 7, 52, 411, 4440, 73886, 2128608, 111533208, 10812478194, 1945437194308, 650378721118910, 404749938336301313, 470163239887698682289, 1022592854829028310302180, 4177826139658552046624979658, 32163829440870460348768017832607, 468021728889827507080865185809438918

Offset

0,4

Links

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

Gus Wiseman, The a(3) = 7 unlabeled non-choosable loop-graphs.

Formula

First differences of A369146.

a(n) = A322700(n) - A369200(n). - Andrew Howroyd, Feb 02 2024

Example

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

Mathematica

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]], p[[i]]}, {i, Length[p]}])], {p, Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n], {1, 2}]], Union@@#==Range[n] && Length[Select[Tuples[#], UnsameQ@@#&]]==0&]]], {n, 0, 4}]

Crossrefs

Without the choice condition we have A322700, labeled A322661.

The complement for exactly n edges is A368984, labeled A333331 (maybe).

The labeled complement is A369140, covering case of A368927.

The labeled version is A369142, covering case of A369141.

This is the covering case of A369146.

The complement is counted by A369200, covering case of A369145.

Without loops we have A369202, covering case of A140637.

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

A000666 counts unlabeled loop-graphs, labeled A006125 (shifted left).

A002494 counts unlabeled covering graphs, labeled A006129.

A007716 counts non-isomorphic multiset partitions, connected A007718.

Cf. A000088, A000612, A005703, A055621, A062740, A134964, A137917, A140638, A367868, A368835, A369199.

Sequence in context: A147962 A329012 A349532 * A162233 A185623 A193881

Adjacent sequences: A369144 A369145 A369146 * A369148 A369149 A369150

Keyword

nonn

Author

Gus Wiseman, Jan 23 2024

Extensions

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

Status

approved