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

Author

Gus Wiseman, Jan 22 2024

Keywords

• nonn

Examples

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

Links

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

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.

Programs

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

Formula

Partial sums of A369147.

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

Extensions

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