login
Number of non-isomorphic set-systems of weight n satisfying a strict version of the axiom of choice.
32

%I #8 Dec 26 2023 08:33:49

%S 1,1,2,4,8,17,39,86,208,508,1304

%N Number of non-isomorphic set-systems of weight n satisfying a strict version of the axiom of choice.

%C A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements.

%C 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.

%e Non-isomorphic representatives of the a(1) = 1 through a(5) = 17 set-systems:

%e {1} {12} {123} {1234} {12345}

%e {1}{2} {1}{23} {1}{234} {1}{2345}

%e {2}{12} {12}{34} {12}{345}

%e {1}{2}{3} {13}{23} {14}{234}

%e {3}{123} {23}{123}

%e {1}{2}{34} {4}{1234}

%e {1}{3}{23} {1}{2}{345}

%e {1}{2}{3}{4} {1}{23}{45}

%e {1}{24}{34}

%e {1}{4}{234}

%e {2}{13}{23}

%e {2}{3}{123}

%e {3}{13}{23}

%e {4}{12}{34}

%e {1}{2}{3}{45}

%e {1}{2}{4}{34}

%e {1}{2}{3}{4}{5}

%t Table[Length[Select[bmp[n], UnsameQ@@#&&And@@UnsameQ@@@#&&Select[Tuples[#], UnsameQ@@#&]!={}&]], {n,0,10}]

%Y For labeled graphs we have A133686, complement A367867.

%Y For unlabeled graphs we have A134964, complement A140637.

%Y For set-systems we have A367902, complement A367903.

%Y These set-systems have BII-numbers A367906, complement A367907.

%Y The complement is A368094, connected A368409.

%Y Repeats allowed: A368098, ranks A368100, complement A368097, ranks A355529.

%Y Minimal multiset partitions not of this type are counted by A368187.

%Y The connected case is A368410.

%Y Factorizations of this type are counted by A368414, complement A368413.

%Y Allowing repeated edges gives A368422, complement A368421.

%Y A000110 counts set-partitions, non-isomorphic A000041.

%Y A003465 counts covering set-systems, unlabeled A055621.

%Y A007716 counts non-isomorphic multiset partitions, connected A007718.

%Y A058891 counts set-systems, unlabeled A000612, connected A323818.

%Y A283877 counts non-isomorphic set-systems, connected A300913.

%Y Cf. A001055, A007717, A302545, A306005, A316983, A319560, A321194, A321405, A330223, A367769, A367901.

%K nonn,more

%O 0,3

%A _Gus Wiseman_, Dec 24 2023