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

0, 0, 1, 8, 60, 471, 4911, 78797, 2207405, 113740613, 10926218807, 1956363413115, 652335084532025, 405402273420833338, 470568642161119515627, 1023063423471189429817807, 4178849203082023236054797465, 32168008290073542372004072630072, 468053896898117580623237189882068990

Offset

0,4

Links

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

Formula

Partial sums of A369147.

a(n) = A000666(n) - A369145(n). - Andrew Howroyd, Feb 02 2024

Example

The a(0) = 0 through a(3) = 8 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{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}]], Select[Tuples[#], UnsameQ@@#&]=={}&]]], {n, 0, 4}]

Crossrefs

Without the choice condition we have A000666, labeled A006125 (shifted).

For a unique choice we have A087803, labeled A088957.

The case without loops is A140637, labeled A367867 (covering A367868).

For exactly n edges we have A368835, labeled A368596.

The labeled complement is A368927, covering A369140.

The labeled version is A369141, covering A369142.

The complement is counted by A369145, covering A369200.

The covering case is A369147.

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

A007716 counts non-isomorphic multiset partitions, connected A007718.

A129271 counts connected choosable simple graphs, unlabeled A005703.

A322661 counts labeled covering loop-graphs, unlabeled A322700.

Cf. A000088, A000612, A006649, A062740, A134964, A137917, A140638, A368600, A368984, A369199.

Sequence in context: A233666 A199526 A129331 * A005990 A160228 A274746

Adjacent sequences: A369143 A369144 A369145 * A369147 A369148 A369149

Keyword

nonn

Author

Gus Wiseman, Jan 22 2024

Extensions

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

Status

approved