login
A367770
Number of sets of nonempty non-singleton subsets of {1..n} satisfying a strict version of the axiom of choice.
18
1, 1, 2, 15, 558, 81282, 39400122, 61313343278, 309674769204452
OFFSET
0,3
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.
Excludes all set-systems with more edges than covered vertices, but this condition is not sufficient.
EXAMPLE
The a(3) = 15 set-systems:
{}
{{1,2}}
{{1,3}}
{{2,3}}
{{1,2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,2},{1,2,3}}
{{1,3},{2,3}}
{{1,3},{1,2,3}}
{{2,3},{1,2,3}}
{{1,2},{1,3},{2,3}}
{{1,2},{1,3},{1,2,3}}
{{1,2},{2,3},{1,2,3}}
{{1,3},{2,3},{1,2,3}}
MATHEMATICA
Table[Length[Select[Subsets[Select[Subsets[Range[n]], Length[#]>1&]], Select[Tuples[#], UnsameQ@@#&]!={}&]], {n, 0, 3}]
CROSSREFS
Set-systems without singletons are counted by A016031, covering A323816.
The version for simple graphs is A133686, covering A367869.
The complement is counted by A367769.
The complement allowing singletons and empty sets is A367901.
Allowing singletons gives A367902, ranks A367906.
The complement allowing singletons is A367903, ranks A367907.
These set-systems have ranks A367906 /\ A326781.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A323818 counts covering connected set-systems, unlabeled A323819.
Sequence in context: A370014 A357856 A177394 * A136463 A361210 A078475
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Dec 05 2023
EXTENSIONS
a(6)-a(8) from Christian Sievers, Jul 28 2024
STATUS
approved