A368409 -id:A368409 - cp's OEIS frontend

A367903 Number of sets of nonempty subsets of {1..n} contradicting a strict version of the axiom of choice.

0, 0, 1, 67, 30997, 2147296425, 9223372036784737528, 170141183460469231731687303625772608225, 57896044618658097711785492504343953926634992332820282019728791606173188627779

Offset: 0

Gus Wiseman, Dec 05 2023

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.

			The a(2) = 1 set-system is {{1},{2},{1,2}}.
The a(3) = 67 set-systems have following 21 non-isomorphic representatives:
  {{1},{2},{1,2}}
  {{1},{2},{3},{1,2}}
  {{1},{2},{3},{1,2,3}}
  {{1},{2},{1,2},{1,3}}
  {{1},{2},{1,2},{1,2,3}}
  {{1},{2},{1,3},{2,3}}
  {{1},{2},{1,3},{1,2,3}}
  {{1},{1,2},{1,3},{2,3}}
  {{1},{1,2},{1,3},{1,2,3}}
  {{1},{1,2},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}
  {{1},{2},{3},{1,2},{1,3}}
  {{1},{2},{3},{1,2},{1,2,3}}
  {{1},{2},{1,2},{1,3},{2,3}}
  {{1},{2},{1,2},{1,3},{1,2,3}}
  {{1},{2},{1,3},{2,3},{1,2,3}}
  {{1},{1,2},{1,3},{2,3},{1,2,3}}
  {{1},{2},{3},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3},{1,2,3}}
  {{1},{2},{1,2},{1,3},{2,3},{1,2,3}}
  {{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Wikipedia, Axiom of choice.

Multisets of multisets of this type are ranked by A355529.
The version without singletons is A367769.
The version for simple graphs is A367867, covering A367868.
The version allowing empty edges is A367901.
The complement is A367902, without singletons A367770, ranks A367906.
For a unique choice (instead of none) we have A367904, ranks A367908.
These set-systems have ranks A367907.
An unlabeled version is A368094, for multiset partitions A368097.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems.
A326031 gives weight of the set-system with BII-number n.
Cf. A007716, A083323, A092918, A102896, A283877, A306445, A355739, A355740, A367862, A367905, A368409, A368413.

Table[Length[Select[Subsets[Rest[Subsets[Range[n]]]], Select[Tuples[#],UnsameQ@@#&]=={}&]],{n,0,3}]

a(n) + A367904(n) + A367772(n) = A058891(n+1) = 2^(2^n-1).

a(5)-a(8) from Christian Sievers, Jul 26 2024

A368413 Number of factorizations of n into positive integers > 1 such that it is not possible to choose a different prime factor of each factor.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 4, 0, 1, 0, 1, 0, 0, 0, 3, 1, 0, 2, 1, 0, 0, 0, 6, 0, 0, 0, 4, 0, 0, 0, 3, 0, 0, 0, 1, 1, 0, 0, 7, 1, 1, 0, 1, 0, 3, 0, 3, 0, 0, 0, 2, 0, 0, 1, 10, 0, 0, 0, 1, 0, 0, 0, 10, 0, 0, 1, 1, 0, 0, 0, 7, 4, 0, 0, 2, 0, 0

Offset: 1

Gus Wiseman, Dec 27 2023

nonn

For example, the factorization f = 2*3*6 has two ways to choose a prime factor of each factor, namely (2,3,2) and (2,3,3), but neither of these has all different elements, so f is counted under a(36).

			The a(1) = 0 through a(24) = 3 factorizations:
 ... 2*2 ... 2*4   3*3 .. 2*2*3 ... 2*8     . 2*3*3 . 2*2*5 ... 2*2*6
             2*2*2                  4*4                         2*3*4
                                    2*2*4                       2*2*2*3
                                    2*2*2*2

For unlabeled graphs: A140637, complement A134964.
For labeled graphs: A367867, A367868, A140638, complement A133686.
For set-systems: A367903, ranks A367907, complement A367902, ranks A367906.
For non-isomorphic set-systems: A368094, A368409, complement A368095.
For non-isomorphic multiset partitions: A368097, A355529, A368411.
Complement for non-isomorphic multiset partitions: A368098, A368100.
The complement is counted by A368414.
For non-isomorphic set multipartitions: A368421, complement A368422.
For divisors instead of prime factors: A370813, complement A370814.
A001055 counts factorizations, strict A045778.
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. A340596, A340653, A367769, A367901, A368187, A368412.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&, Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], Select[Tuples[First/@FactorInteger[#]&/@#], UnsameQ@@#&]=={}&]],{n,100}]

a(n) + A368414(n) = A001055(n).

A368097 Number of non-isomorphic multiset partitions of weight n contradicting a strict version of the axiom of choice.

Original entry on oeis.org

0, 0, 1, 3, 12, 37, 133, 433, 1516, 5209, 18555

Offset: 0

Gus Wiseman, Dec 25 2023

A multiset partition is a finite multiset of finite nonempty multisets. The weight of a multiset partition is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

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.

			Non-isomorphic representatives of the a(2) = 1 through a(4) = 12 multiset partitions:
  {{1},{1}}  {{1},{1,1}}    {{1},{1,1,1}}
             {{1},{1},{1}}  {{1,1},{1,1}}
             {{1},{2},{2}}  {{1},{1},{1,1}}
                            {{1},{1},{2,2}}
                            {{1},{1},{2,3}}
                            {{1},{2},{1,2}}
                            {{1},{2},{2,2}}
                            {{2},{2},{1,2}}
                            {{1},{1},{1},{1}}
                            {{1},{1},{2},{2}}
                            {{1},{2},{2},{2}}
                            {{1},{2},{3},{3}}

Wikipedia, Axiom of choice.

The case of unlabeled graphs appears to be A140637, complement A134964.
These multiset partitions have ranks A355529.
The case of labeled graphs is A367867, complement A133686.
Set-systems not of this type are A367902, ranks A367906.
Set-systems of this type are A367903, ranks A367907.
For set-systems we have A368094, complement A368095.
The complement is A368098, ranks A368100, connected case A368412.
Minimal multiset partitions of this type are ranked by A368187.
The connected case is A368411.
Factorizations of this type are counted by A368413, complement A368414.
For set multipartitions we have A368421, complement A368422.
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. A302545, A316983, A317533, A319616, A321405, A367905, A368409, A368410.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]] /@ Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort/@(#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]], {s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
Table[Length[Union[brute/@Select[mpm[n], Select[Tuples[#],UnsameQ@@#&]=={}&]]], {n,0,6}]

A368414 Number of factorizations of n into positive integers > 1 such that it is possible to choose a different prime factor of each factor.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 5, 1, 1, 2, 2, 2, 5, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 1, 2, 5, 1, 3, 2, 5, 1, 6, 1, 2, 3, 3, 2, 5, 1, 5, 1, 2, 1, 9, 2, 2, 2

Offset: 1

Gus Wiseman, Dec 29 2023

nonn

For example, the factorization f = 2*3*6 has two ways to choose a prime factor of each factor, namely (2,3,2) and (2,3,3), but neither of these has all different elements, so f is not counted under a(36).

			The a(n) factorizations for selected n:
  1    6      12     24      30       60        72      120
       2*3    2*6    2*12    2*15     2*30      2*36    2*60
              3*4    3*8     3*10     3*20      3*24    3*40
                     4*6     5*6      4*15      4*18    4*30
                             2*3*5    5*12      6*12    5*24
                                      6*10      8*9     6*20
                                      2*3*10            8*15
                                      2*5*6             10*12
                                      3*4*5             2*3*20
                                                        2*5*12
                                                        2*6*10
                                                        3*4*10
                                                        3*5*8
                                                        4*5*6

For labeled graphs: A133686, complement A367867, A367868, A140638.
For unlabeled graphs: A134964, complement A140637.
For set-systems: A367902, ranks A367906, complement A367903, ranks A367907.
For non-isomorphic set-systems: A368095, complement A368094, A368409.
Complementary non-isomorphic multiset partitions: A368097, A355529, A368411.
For non-isomorphic multiset partitions: A368098, A368100.
The complement is counted by A368413.
For non-isomorphic set multipartitions: A368422, complement A368421.
For divisors instead of prime factors: A370813, complement A370814.
A001055 counts factorizations, strict A045778.
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. A340596, A340653, A367769, A367901, A368187, A368412, A368413.

facs[n_]:=If[n<=1,{{}},Join @@ Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]], {d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], Select[Tuples[First/@FactorInteger[#]&/@#], UnsameQ@@#&]!={}&]],{n,100}]

a(n) = A001055(n) - A368413(n).

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

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 5, 12, 36, 97, 291

Offset: 0

Gus Wiseman, Dec 23 2023

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. Weight is generally not the same as number of vertices.

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.

			Non-isomorphic representatives of the a(5) = 1 through a(7) = 12 set-systems:
  {{1},{2},{3},{2,3}}  {{1},{2},{1,3},{2,3}}    {{1},{2},{1,2},{3,4,5}}
                       {{1},{2},{3},{1,2,3}}    {{1},{3},{2,3},{1,2,3}}
                       {{2},{3},{1,3},{2,3}}    {{1},{4},{1,4},{2,3,4}}
                       {{3},{4},{1,2},{3,4}}    {{2},{3},{2,3},{1,2,3}}
                       {{1},{2},{3},{4},{3,4}}  {{3},{1,2},{1,3},{2,3}}
                                                {{1},{2},{3},{1,3},{2,3}}
                                                {{1},{2},{3},{2,4},{3,4}}
                                                {{1},{2},{3},{4},{2,3,4}}
                                                {{1},{3},{4},{2,4},{3,4}}
                                                {{1},{4},{5},{2,3},{4,5}}
                                                {{2},{3},{4},{1,2},{3,4}}
                                                {{1},{2},{3},{4},{5},{4,5}}

Wikipedia, Axiom of choice.

The case of unlabeled graphs is A140637, complement A134964.
The case of labeled graphs is A367867, complement A133686.
The labeled version is A367903, ranks A367907.
The complement is counted by A368095, connected A368410.
Repeats allowed: A368097, ranks A355529, complement A368098, ranks A368100.
Minimal multiset partitions of this type are ranked by A368187.
The connected case is A368409.
Factorizations of this type are counted by A368413, complement A368414.
Allowing repeated edges gives A368421, complement A368422.
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. A302545, A306005, A316983, A317533, A319616, A321155, A321405, A326031, A330223, A330227, A367905.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]] /@ Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort/@(#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]], {s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
Table[Length[Union[brute/@Select[mpm[n], UnsameQ@@#&&And@@UnsameQ@@@# && Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,8}]

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

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Dec 24 2023

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.

			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}

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.

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

A368098 Number of non-isomorphic multiset partitions of weight n satisfying a strict version of the axiom of choice.

Original entry on oeis.org

1, 1, 3, 7, 21, 54, 165, 477, 1501, 4736, 15652

Offset: 0

Gus Wiseman, Dec 25 2023

A multiset partition is a finite multiset of finite nonempty multisets. The weight of a multiset partition is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

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.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 21 multiset partitions:
  {{1}}  {{1,1}}    {{1,1,1}}      {{1,1,1,1}}
         {{1,2}}    {{1,2,2}}      {{1,1,2,2}}
         {{1},{2}}  {{1,2,3}}      {{1,2,2,2}}
                    {{1},{2,2}}    {{1,2,3,3}}
                    {{1},{2,3}}    {{1,2,3,4}}
                    {{2},{1,2}}    {{1},{1,2,2}}
                    {{1},{2},{3}}  {{1,1},{2,2}}
                                   {{1,2},{1,2}}
                                   {{1},{2,2,2}}
                                   {{1,2},{2,2}}
                                   {{1},{2,3,3}}
                                   {{1,2},{3,3}}
                                   {{1},{2,3,4}}
                                   {{1,2},{3,4}}
                                   {{1,3},{2,3}}
                                   {{2},{1,2,2}}
                                   {{3},{1,2,3}}
                                   {{1},{2},{3,3}}
                                   {{1},{2},{3,4}}
                                   {{1},{3},{2,3}}
                                   {{1},{2},{3},{4}}

Wikipedia, Axiom of choice.

The case of labeled graphs is A133686, complement A367867.
The case of unlabeled graphs is A134964, complement A140637 (apparently).
Set-systems of this type are A367902, ranks A367906, connected A368410.
The complimentary set-systems are A367903, ranks A367907, connected A368409.
For set-systems we have A368095, complement A368094.
The complement is A368097, ranks A355529.
These multiset partitions have ranks A368100.
The connected case is A368412, complement A368411.
Factorizations of this type are counted by A368414, complement A368413.
For set multipartitions we have 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. A302545, A306005, A316983, A317533, A319616, A330223, A330227, A368187.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]] /@ Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort/@(#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]], {s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
Table[Length[Union[brute/@Select[mpm[n], Select[Tuples[#],UnsameQ@@#&]!={}&]]], {n,0,6}]

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

Original entry on oeis.org

1, 1, 2, 4, 9, 18, 43, 95, 233, 569

Offset: 0

Gus Wiseman, Dec 26 2023

A set multipartition is a finite multiset of finite nonempty sets. The weight of a set multipartition is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

The axiom of choice says that, given any sequence of nonempty sets, it is possible to choose a sequence containing an element from each. In the strict version, the elements of this sequence must be distinct, meaning none is chosen more than once.

			Non-isomorphic representatives of the a(1) = 1 through a(5) = 18 set multipartitions:
  {{1}}  {{1,2}}    {{1,2,3}}      {{1,2,3,4}}        {{1,2,3,4,5}}
         {{1},{2}}  {{1},{2,3}}    {{1,2},{1,2}}      {{1},{2,3,4,5}}
                    {{2},{1,2}}    {{1},{2,3,4}}      {{1,2},{3,4,5}}
                    {{1},{2},{3}}  {{1,2},{3,4}}      {{1,4},{2,3,4}}
                                   {{1,3},{2,3}}      {{2,3},{1,2,3}}
                                   {{3},{1,2,3}}      {{4},{1,2,3,4}}
                                   {{1},{2},{3,4}}    {{1},{2,3},{2,3}}
                                   {{1},{3},{2,3}}    {{1},{2},{3,4,5}}
                                   {{1},{2},{3},{4}}  {{1},{2,3},{4,5}}
                                                      {{1},{2,4},{3,4}}
                                                      {{1},{4},{2,3,4}}
                                                      {{2},{1,3},{2,3}}
                                                      {{2},{3},{1,2,3}}
                                                      {{3},{1,3},{2,3}}
                                                      {{4},{1,2},{3,4}}
                                                      {{1},{2},{3},{4,5}}
                                                      {{1},{2},{4},{3,4}}
                                                      {{1},{2},{3},{4},{5}}

Wikipedia, Axiom of choice.

The case of unlabeled graphs is A134964, complement A140637.
Set multipartitions have ranks A302478, cf. A073576.
The case of labeled graphs is A133686, complement A367867.
The complement without repeats is A368094 connected A368409.
Without repeats we have A368095, connected A368410.
The complement allowing repeats is A368097, ranks A355529.
Allowing repeated elements gives A368098, ranks A368100.
Factorizations of this type are counted by A368414, complement A368413.
The complement is counted by 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. A302545, A306005, A317533, A318360, A367903.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]&/@sps[Range[n]]],{s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
Table[Length[Union[brute /@ Select[mpm[n],And@@UnsameQ@@@#&&Select[Tuples[#], UnsameQ@@#&]!={}&]]],{n,0,6}]

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

Original entry on oeis.org

0, 1, 1, 2, 3, 7, 15, 32, 80, 198, 528

Offset: 0

Gus Wiseman, Dec 25 2023

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. Weight is generally not the same as number of vertices.

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.

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

Wikipedia, Axiom of choice.

For unlabeled graphs we have A005703, connected case of A134964.
For labeled graphs we have A129271, connected case of A133686.
The complement for labeled graphs is A140638, connected case of A367867.
The complement without connectedness is A367903, ranks A367907.
Without connectedness we have A368095, ranks A367906,
Complement with repeats: A368097, connected case of A368411, ranks A355529.
The complement is counted by A368409, connected case of A368094.
With repeats allowed: A368412, connected case of A368098, ranks A368100.
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, A140637, A302545, A306005, A321194, A321405, A367902, A368414, A368422.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort/@(#/.x_Integer:>s[[x]])]& /@ sps[Range[n]]],{s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort/@(m/.Rule@@@Table[{i,p[[i]]}, {i,Length[p]}])],{p,Permutations[Union@@m]}]]];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]}, If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[brute/@Select[mpm[n], UnsameQ@@#&&And@@UnsameQ@@@#&&Length[csm[#]]==1&&Select[Tuples[#], UnsameQ@@#&]!={}&]]],{n,0,6}]

A368421 Number of non-isomorphic set multipartitions of weight n contradicting a strict version of the axiom of choice.

Original entry on oeis.org

0, 0, 1, 2, 7, 16, 47, 116, 325, 861

Offset: 0

Gus Wiseman, Dec 26 2023

A set multipartition is a finite multiset of finite nonempty sets. The weight of a set multipartition is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

The axiom of choice says that, given any sequence of nonempty sets Y, it is possible to choose a sequence containing an element from each. In the strict version, the elements of this sequence must be distinct, meaning none is chosen more than once.

			Non-isomorphic representatives of the a(2) = 1 through a(5) = 16 set multipartitions:
  {{1},{1}}  {{1},{1},{1}}  {{1},{1},{2,3}}    {{1},{1},{2,3,4}}
             {{1},{2},{2}}  {{1},{2},{1,2}}    {{2},{1,2},{1,2}}
                            {{2},{2},{1,2}}    {{3},{3},{1,2,3}}
                            {{1},{1},{1},{1}}  {{1},{1},{1},{2,3}}
                            {{1},{1},{2},{2}}  {{1},{1},{3},{2,3}}
                            {{1},{2},{2},{2}}  {{1},{2},{2},{1,2}}
                            {{1},{2},{3},{3}}  {{1},{2},{2},{3,4}}
                                               {{1},{2},{3},{2,3}}
                                               {{1},{3},{3},{2,3}}
                                               {{2},{2},{2},{1,2}}
                                               {{1},{1},{1},{1},{1}}
                                               {{1},{1},{2},{2},{2}}
                                               {{1},{2},{2},{2},{2}}
                                               {{1},{2},{2},{3},{3}}
                                               {{1},{2},{3},{3},{3}}
                                               {{1},{2},{3},{4},{4}}

Wikipedia, Axiom of choice.

The case of unlabeled graphs is A140637, complement A134964.
Set multipartitions have ranks A302478, cf. A073576.
The case of labeled graphs is A367867, complement A133686.
With distinct edges we have A368094 connected A368409.
The complement with distinct edges is A368095, connected A368410.
Allowing repeated elements gives A368097, ranks A355529.
The complement allowing repeats is A368098, ranks A368100.
Factorizations of this type are counted by A368413, complement A368414.
The complement is counted by A368422.
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. A302545, A306005, A316983, A317533, A318360, A367903, A367905, A367907.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]&/@sps[Range[n]]],{s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
Table[Length[Union[brute /@ Select[mpm[n],And@@UnsameQ@@@#&&Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,6}]

cp's OEIS Frontend

A367903 Number of sets of nonempty subsets of {1..n} contradicting a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A368413 Number of factorizations of n into positive integers > 1 such that it is not possible to choose a different prime factor of each factor.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A368097 Number of non-isomorphic multiset partitions of weight n contradicting a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A368414 Number of factorizations of n into positive integers > 1 such that it is possible to choose a different prime factor of each factor.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A368098 Number of non-isomorphic multiset partitions of weight n satisfying a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs