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

0, 0, 0, 3, 66, 1380, 31460, 800625, 22758918, 718821852, 25057509036, 957657379437, 39878893266795, 1799220308202603, 87502582432459584, 4566246347310609247, 254625879822078742956, 15115640124974801925030, 952050565540607423524658, 63425827673509972464868323

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(3) = 3 set-systems:
  {{1},{2},{1,2}}
  {{1},{3},{1,3}}
  {{2},{3},{2,3}}
		

Links

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

Crossrefs

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

The complement appears to be A333331.

For covering pairs we have A367868.

Allowing edges of any positive size gives A368600, any length A367903.

The covering case is A368730.

The unlabeled version is A368835.

A000085 counts set partitions into singletons or pairs.

A006125 counts graphs, unlabeled A000088.

A058891 counts set-systems (without singletons A016031), unlabeled A000612.

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

A111924 counts set partitions into singletons or pairs by length.

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

A369141 counts non-choosable loop-graphs, covering A369142.

A369146 counts unlabeled non-choosable loop-graphs, covering A369147.

Cf. A000272, A000666, A057500, A129271, A133686, A367769, A367863, A367867, A367869, A367901, A367907, A368097, A369199.

Programs

Mathematica

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

Extensions

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