A368730 Number of n-element sets of singletons or pairs of distinct elements of {1..n} with union {1..n}, or loop-graphs covering n vertices with n edges, such that it is not possible to choose a different element from each.

0, 0, 0, 0, 6, 180, 4560, 117600, 3234588, 96119982, 3092585310, 107542211535, 4029055302855, 162040513972623, 6970457656110039, 319598974394563500, 15568332397812799920, 803271954062642638830, 43778508937914677872788, 2513783434620146896920843

Offset: 0

Author

Gus Wiseman, Jan 04 2024

Keywords

• nonn

Comments

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

Examples

			The a(4) = 6 set-systems:
  {{1},{2},{1,2},{3,4}}
  {{1},{3},{1,3},{2,4}}
  {{1},{4},{1,4},{2,3}}
  {{2},{3},{1,4},{2,3}}
  {{2},{4},{1,3},{2,4}}
  {{3},{4},{1,2},{3,4}}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• Eric Weisstein's World of Mathematics, Graph Loop.
• ProofWiki, Definition:Loop-Graph

Crossrefs

The case of a unique choice appears to be A000272.

The version without the choice condition is A368597, non-covering A014068.

The complement appears to be A333331.

The non-covering case is A368596, allowing edges of any size A368600.

Allowing any number of edges of any size gives A367903, ranks A367907.

Allowing any number of non-singletons gives A367868, non-covering A367867.

A000085 counts set partitions into singletons or pairs.

A006125 counts graphs, unlabeled A000088.

A006129 counts covering graphs, unlabeled A002494.

A100861 counts set partitions into singletons or pairs by number of pairs.

A111924 counts set partitions into singletons or pairs by length.

A322661 counts labeled covering half-loop-graphs, connected A062740.

Cf. A000666, A116508, A133686, A367863, A367869, A367901, A368532.

Programs

Mathematica

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

Formula

a(n) = A368596(n) + A368597(n) - A014068(n). - Andrew Howroyd, Jan 10 2024

Extensions

Terms a(7) and beyond from Andrew Howroyd, Jan 10 2024