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,4

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.

Links

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

Example

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

Mathematica

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

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.

Sequence in context: A238471 A259457 A157543 * A157984 A187547 A157554

Adjacent sequences: A368593 A368594 A368595 * A368597 A368598 A368599

Keyword

nonn

Author

Gus Wiseman, Jan 04 2024

Extensions

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

Status

approved