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

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

Offset: 0

Author

Gus Wiseman, Dec 24 2023

Keywords

• nonn
• more

Comments

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.

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

			Non-isomorphic representatives of the a(1) = 1 through a(5) = 17 set-systems:
  {1}  {12}    {123}      {1234}        {12345}
       {1}{2}  {1}{23}    {1}{234}      {1}{2345}
               {2}{12}    {12}{34}      {12}{345}
               {1}{2}{3}  {13}{23}      {14}{234}
                          {3}{123}      {23}{123}
                          {1}{2}{34}    {4}{1234}
                          {1}{3}{23}    {1}{2}{345}
                          {1}{2}{3}{4}  {1}{23}{45}
                                        {1}{24}{34}
                                        {1}{4}{234}
                                        {2}{13}{23}
                                        {2}{3}{123}
                                        {3}{13}{23}
                                        {4}{12}{34}
                                        {1}{2}{3}{45}
                                        {1}{2}{4}{34}
                                        {1}{2}{3}{4}{5}
		

Crossrefs

For labeled graphs we have A133686, complement A367867.

For unlabeled graphs we have A134964, complement A140637.

For set-systems we have A367902, complement A367903.

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

The complement is A368094, connected A368409.

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

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

The connected case is A368410.

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

Allowing repeated edges gives A368422, complement A368421.

A000110 counts set-partitions, non-isomorphic A000041.

A003465 counts covering set-systems, unlabeled A055621.

A007716 counts non-isomorphic multiset partitions, connected A007718.

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

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

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

Programs

Mathematica

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