A058891 -id:A058891 - cp's OEIS frontend

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

0, 0, 0, 0, 1, 0, 3, 5, 16, 41, 130

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(4) = 1 through a(8) = 16 set-systems:
  {1}{2}{12}  .  {1}{2}{13}{23}  {1}{3}{23}{123}    {1}{5}{15}{2345}
                 {1}{2}{3}{123}  {1}{4}{14}{234}    {2}{13}{23}{123}
                 {2}{3}{13}{23}  {2}{3}{23}{123}    {3}{13}{23}{123}
                                 {3}{12}{13}{23}    {3}{4}{34}{1234}
                                 {1}{2}{3}{13}{23}  {1}{2}{13}{24}{34}
                                                    {1}{2}{3}{14}{234}
                                                    {1}{2}{3}{23}{123}
                                                    {1}{2}{3}{4}{1234}
                                                    {1}{3}{4}{14}{234}
                                                    {2}{3}{12}{13}{23}
                                                    {2}{3}{13}{24}{34}
                                                    {2}{3}{14}{24}{34}
                                                    {2}{3}{4}{14}{234}
                                                    {2}{4}{13}{24}{34}
                                                    {3}{4}{13}{24}{34}
                                                    {3}{4}{14}{24}{34}

Wikipedia, Axiom of choice.

For unlabeled graphs we have A140636, connected case of A140637.
For labeled graphs: A140638, connected case of A367867 (complement A133686).
This is the connected case of A368094.
The complement is A368410, connected case of A368095.
Allowing repeats: A368411, connected case of A368097, ranks A355529.
Complement with repeats: A368412, connected case of A368098, ranks A368100.
Allowing repeat edges only: connected case of 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. A134964, A302545, A306005, A317533, A321405, A326031, A367903, A367907, A368187, A368413.

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}]

A370640 Number of maximal subsets of {1..n} such that it is possible to choose a different binary index of each element.

Original entry on oeis.org

1, 1, 1, 3, 3, 8, 17, 32, 32, 77, 144, 242, 383, 580, 843, 1201, 1201, 2694, 4614, 7096, 10219, 14186, 19070, 25207, 32791, 42160, 53329, 66993, 82811, 101963, 124381, 151286, 151286, 324695, 526866, 764438, 1038089, 1358129, 1725921, 2154668, 2640365, 3202985

Offset: 0

Gus Wiseman, Mar 10 2024

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

Also choices of A070939(n) elements of {1..n} such that it is possible to choose a different binary index of each.

			The a(0) = 1 through a(6) = 17 subsets:
  {}  {1}  {1,2}  {1,2}  {1,2,4}  {1,2,4}  {1,2,4}
                  {1,3}  {1,3,4}  {1,2,5}  {1,2,5}
                  {2,3}  {2,3,4}  {1,3,4}  {1,2,6}
                                  {1,3,5}  {1,3,4}
                                  {2,3,4}  {1,3,5}
                                  {2,3,5}  {1,3,6}
                                  {2,4,5}  {1,4,6}
                                  {3,4,5}  {1,5,6}
                                           {2,3,4}
                                           {2,3,5}
                                           {2,3,6}
                                           {2,4,5}
                                           {2,5,6}
                                           {3,4,5}
                                           {3,4,6}
                                           {3,5,6}
                                           {4,5,6}
The a(0) = 1 through a(6) = 17 set-systems:
    {1}  {1}{2}  {1}{2}   {1}{2}{3}   {1}{2}{3}    {1}{2}{3}
                 {1}{12}  {1}{12}{3}  {1}{12}{3}   {1}{12}{3}
                 {2}{12}  {2}{12}{3}  {1}{2}{13}   {1}{2}{13}
                                      {2}{12}{3}   {1}{2}{23}
                                      {2}{3}{13}   {1}{3}{23}
                                      {1}{12}{13}  {2}{12}{3}
                                      {12}{3}{13}  {2}{3}{13}
                                      {2}{12}{13}  {1}{12}{13}
                                                   {1}{12}{23}
                                                   {1}{13}{23}
                                                   {12}{3}{13}
                                                   {12}{3}{23}
                                                   {2}{12}{13}
                                                   {2}{12}{23}
                                                   {2}{13}{23}
                                                   {3}{13}{23}
                                                   {12}{13}{23}

Dominated by A357812.
The version for set-systems is A368601, max of A367902 (complement A367903).
For prime indices we have A370585, with n A370590, see also A370591.
This is the maximal case of A370636 (complement A370637).
The case of a unique choice is A370638.
The case containing n is A370641, non-maximal A370639.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A058891 counts set-systems, A003465 covering, A323818 connected.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A307984 counts Q-bases of logarithms of positive integers.
A355741 counts choices of a prime factor of each prime index.
Cf. A133686, A326031, A326702, A367905, A367909, A367912, A368109, A368110, A370592, A370642.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Table[Length[Select[Subsets[Range[n],{IntegerLength[n,2]}], Select[Tuples[bpe/@#],UnsameQ@@#&]!={}&]],{n,0,10}]

lista(nn) = my(b, m=Map(Mat([[[]], 1])), t, u, v, w, z); for(n=0, nn, t=Mat(m)~; b=Vecrev(binary(n)); u=select(i->b[i], [1..#b]); for(i=1, #t, v=t[1, i]; w=List([]); for(j=1, #v, for(k=1, #u, if(!setsearch(v[j], u[k]), listput(w, setunion(v[j], [u[k]]))))); w=Set(w); if(#w, z=0; mapisdefined(m, w, &z); mapput(m, w, z+t[2, i]))); print1(mapget(m, [[1..#b]]), ", ")); \\ Jinyuan Wang, Mar 28 2025

More terms from Jinyuan Wang, Mar 28 2025

A327105 BII-numbers of set-systems with minimum degree 1.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43, 44, 46, 48, 49, 50, 56, 57, 58, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 80, 81, 88, 89, 96, 98, 104, 106, 128

Offset: 1

Gus Wiseman, Aug 26 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

In a set-system, the degree of a vertex is the number of edges containing it.

			The sequence of all set-systems with minimum degree 1 together with their BII-numbers begins:
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  12: {{1,2},{3}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  15: {{1},{2},{1,2},{3}}
  16: {{1,3}}
  17: {{1},{1,3}}
  18: {{2},{1,3}}
  19: {{1},{2},{1,3}}
  20: {{1,2},{1,3}}
  21: {{1},{1,2},{1,3}}

Positions of 1's in A327103.
BII-numbers for minimum degree > 1 are A327107.
Graphs with minimum degree 1 are counted by A245797, with covering case A327227.
Set-systems with minimum degree 1 are counted by A327228, with covering case A327229.
Cf. A000120, A029931, A048793, A058891, A070939, A326031, A326701, A326786, A327041, A327104, A327230.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[0,100],If[#==0,0,Min@@Length/@Split[Sort[Join@@bpe/@bpe[#]]]]==1&]

A367917 BII-numbers of set-systems with the same number of edges as covered vertices.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 8, 9, 10, 11, 13, 14, 17, 19, 21, 22, 24, 26, 28, 34, 35, 37, 38, 40, 41, 44, 49, 50, 52, 56, 67, 69, 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112, 128, 129, 130, 131, 133, 134, 136, 137, 138, 139, 141, 142, 145, 147, 149, 150, 152

Offset: 1

Gus Wiseman, Dec 12 2023

nonn

A binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion. A set-system is a finite set of finite nonempty sets. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.

			The terms together with the corresponding set-systems begin:
   0: {}
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  17: {{1},{1,3}}
  19: {{1},{2},{1,3}}
  21: {{1},{1,2},{1,3}}
  22: {{2},{1,2},{1,3}}
  24: {{3},{1,3}}
  26: {{2},{3},{1,3}}
  28: {{1,2},{3},{1,3}}
  34: {{2},{2,3}}
  35: {{1},{2},{2,3}}
  37: {{1},{1,2},{2,3}}

These set-systems are counted by A054780 and A367916, A368186.
Graphs of this type are A367862, covering A367863, unlabeled A006649.
A003465 counts set-systems covering {1..n}, unlabeled A055621.
A048793 lists binary indices, length A000120, sum A029931.
A058891 counts set-systems, connected A323818, unlabeled A000612.
A070939 gives length of binary expansion.
A136556 counts set-systems on {1..n} with n edges.
Cf. A057500, A059201, A072639, A096111, A116508, A309326, A326031, A326702, A326753, A326754, A367770, A367902, A367905.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]],1];
Select[Range[0,100], Length[bpe[#]]==Length[Union@@bpe/@bpe[#]]&]

A370639 Number of subsets of {1..n} containing n such that it is possible to choose a different binary index of each element.

Original entry on oeis.org

0, 1, 2, 3, 7, 10, 15, 22, 61, 81, 112, 154, 207, 276, 355, 464, 1771, 2166, 2724, 3445, 4246, 5292, 6420, 7922, 9586, 11667, 13768, 16606, 19095, 22825, 26498, 31421, 187223, 213684, 247670, 289181, 331301, 385079, 440411, 510124, 575266, 662625, 747521

Offset: 0

Gus Wiseman, Mar 08 2024

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

			The a(0) = 0 through a(6) = 15 subsets:
  .  {1}  {2}    {3}    {4}      {5}      {6}
          {1,2}  {1,3}  {1,4}    {1,5}    {1,6}
                 {2,3}  {2,4}    {2,5}    {2,6}
                        {3,4}    {3,5}    {3,6}
                        {1,2,4}  {4,5}    {4,6}
                        {1,3,4}  {1,2,5}  {5,6}
                        {2,3,4}  {1,3,5}  {1,2,6}
                                 {2,3,5}  {1,3,6}
                                 {2,4,5}  {1,4,6}
                                 {3,4,5}  {1,5,6}
                                          {2,3,6}
                                          {2,5,6}
                                          {3,4,6}
                                          {3,5,6}
                                          {4,5,6}

Wikipedia, Axiom of choice.

Simple graphs of this type are counted by A133686, covering A367869.
Unlabeled graphs of this type are counted by A134964, complement A140637.
Simple graphs not of this type are counted by A367867, covering A367868.
Set systems of this type are counted by A367902, ranks A367906.
Set systems not of this type are counted by A367903, ranks A367907.
Set systems uniquely of this type are counted by A367904, ranks A367908.
Unlabeled multiset partitions of this type are A368098, complement A368097.
A version for MM-numbers of multisets is A368100, complement A355529.
Factorizations of this type are A368414/A370814, complement A368413/A370813.
For prime instead of binary indices we have A370586, differences of A370582.
The complement for prime indices is A370587, differences of A370583.
The complement is counted by A370589, differences of A370637.
Partial sums are A370636.
The complement has partial sums A370637/A370643, minima A370642/A370644.
The case of a unique choice is A370641, differences of A370638.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A058891 counts set-systems, A003465 covering, A323818 connected.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A326031 gives weight of the set-system with BII-number n.
Cf. A000612, A326702, A355739, A355740, A367770, A367772, A367905, A367909, A367912, A368094, A368095, A368109, A370640.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n] && Select[Tuples[bpe/@#],UnsameQ@@#&]!={}&]],{n,0,10}]

First differences of A370636.

a(19)-a(42) from Alois P. Heinz, Mar 09 2024

A327101 BII-numbers of 2-cut-connected set-systems (cut-connectivity >= 2).

Original entry on oeis.org

4, 5, 6, 7, 16, 17, 24, 25, 32, 34, 40, 42, 52, 53, 54, 55, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107

Offset: 1

Gus Wiseman, Aug 22 2019

nonn

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

A set-system is 2-cut-connected if any single vertex can be removed (along with any empty edges) without making the set-system disconnected or empty. Except for cointersecting set-systems (A326853), this is the same as 2-vertex-connectivity.

			The sequence of all 2-cut-connected set-systems together with their BII-numbers begins:
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
  16: {{1,3}}
  17: {{1},{1,3}}
  24: {{3},{1,3}}
  25: {{1},{3},{1,3}}
  32: {{2,3}}
  34: {{2},{2,3}}
  40: {{3},{2,3}}
  42: {{2},{3},{2,3}}
  52: {{1,2},{1,3},{2,3}}
  53: {{1},{1,2},{1,3},{2,3}}
  54: {{2},{1,2},{1,3},{2,3}}
  55: {{1},{2},{1,2},{1,3},{2,3}}
  60: {{1,2},{3},{1,3},{2,3}}
  61: {{1},{1,2},{3},{1,3},{2,3}}
  62: {{2},{1,2},{3},{1,3},{2,3}}
  63: {{1},{2},{1,2},{3},{1,3},{2,3}}

Positions of numbers >= 2 in A326786.
2-cut-connected graphs are counted by A013922, if we assume A013922(2) = 0.
2-cut-connected integer partitions are counted by A322387.
BII-numbers for cut-connectivity 2 are A327082.
BII-numbers for cut-connectivity 1 are A327098.
BII-numbers for non-spanning edge-connectivity >= 2 are A327102.
BII-numbers for spanning edge-connectivity >= 2 are A327109.
Covering 2-cut-connected set-systems are counted by A327112.
Covering set-systems with cut-connectivity 2 are counted by A327113.
The labeled cut-connectivity triangle is A327125, with unlabeled version A327127.
Cf. A000120, A002218, A048793, A070939, A259862, A322388, A326031, A326749, A327097, A327108.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
Select[Range[0,100],cutConnSys[Union@@bpe/@bpe[#],bpe/@bpe[#]]>=2&]

If (*) is intersection and (-) is complement, we have A327101 * A326704 = A326751 - A058891, i.e., the intersection of A327101 (this sequence) with A326704 (antichains) is the complement of A058891 (singletons) in A326751 (blobs).

A357135 Take the k-th composition in standard order for each part k of the n-th composition in standard order; then concatenate.

Original entry on oeis.org

1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 3, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1

Offset: 0

Gus Wiseman, Sep 26 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			Triangle begins:
   0:
   1: 1
   2: 2
   3: 1 1
   4: 1 1
   5: 2 1
   6: 1 2
   7: 1 1 1
   8: 3
   9: 1 1 1
  10: 2 2
  11: 2 1 1
  12: 1 1 1
  13: 1 2 1
  14: 1 1 2
  15: 1 1 1 1

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
Row n is the A357134(n)-th composition in standard order.
The version for Heinz numbers of partitions is A357139, cf. A003963.
Row sums are A357186, differences A357187.
Cf. A000120, A001511, A029931, A048896, A058891, A070939, A096111, A329395, A333766, A335404, A357137.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Join@@Table[Join@@stc/@stc[n],{n,0,30}]

Row n is the A357134(n)-th composition in standard order.

A367913 Least number k such that there are exactly n ways to choose a multiset consisting of a binary index of each binary index of k.

Original entry on oeis.org

1, 4, 64, 20, 68, 320, 52, 84, 16448, 324, 832, 116, 1104, 308, 816, 340, 836, 848, 1108, 1136, 1360, 3152, 16708, 372, 5188, 5216, 852, 880, 2884, 1364, 13376, 1392, 3184, 3424, 17220, 5204, 5220, 2868, 5728, 884, 19536, 66896, 2900, 1396, 21572, 3188, 3412

Offset: 1

Gus Wiseman, Dec 16 2023

nonn

A binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion. For example, 18 has reversed binary expansion (0,1,0,0,1) and binary indices {2,5}.

			The terms together with the corresponding set-systems begin:
      1: {{1}}
      4: {{1,2}}
     64: {{1,2,3}}
     20: {{1,2},{1,3}}
     68: {{1,2},{1,2,3}}
    320: {{1,2,3},{1,4}}
     52: {{1,2},{1,3},{2,3}}
     84: {{1,2},{1,3},{1,2,3}}
  16448: {{1,2,3},{1,2,3,4}}
    324: {{1,2},{1,2,3},{1,4}}
    832: {{1,2,3},{1,4},{2,4}}
    116: {{1,2},{1,3},{2,3},{1,2,3}}

A version for multisets and divisors is A355734.
With distinctness we have A367910, firsts of A367905, sorted A367911.
Positions of first appearances in A367912.
The sorted version is A367915.
For sequences we have A368111, firsts of A368109, sorted A368112.
For sets we have A368184, firsts of A368183, sorted A368185.
A048793 lists binary indices, length A000120, sum A029931.
A058891 counts set-systems, covering A003465, connected A323818.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
Cf. A072639, A309326, A326031, A326702, A326749, A326753, A355733, A355741, A355744.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
spnm[y_]:=Max@@NestWhile[Most,y,Union[#]!=Range[0,Max@@#]&];
c=Table[Length[Union[Sort/@Tuples[bpe/@bpe[n]]]],{n,1000}];
Table[Position[c,n][[1,1]],{n,spnm[c]}]

A367915 Sorted positions of first appearances in A367912 (number of multisets that can be obtained by choosing a binary index of each binary index).

Original entry on oeis.org

1, 4, 20, 52, 64, 68, 84, 116, 308, 320, 324, 340, 372, 816, 832, 836, 848, 852, 880, 884, 1104, 1108, 1136, 1360, 1364, 1392, 1396, 1904, 1908, 2868, 2884, 2900, 2932, 3152, 3184, 3188, 3412, 3424, 3440, 3444, 3952, 3956, 5188, 5204, 5216, 5220, 5236, 5476

Offset: 1

Gus Wiseman, Dec 16 2023

nonn

A binary index of n (row n of A048793) is any position of a 1 in its reversed binary expansion. For example, 18 has reversed binary expansion (0,1,0,0,1) and binary indices {2,5}.

			The terms together with the corresponding set-systems begin:
     1: {{1}}
     4: {{1,2}}
    20: {{1,2},{1,3}}
    52: {{1,2},{1,3},{2,3}}
    64: {{1,2,3}}
    68: {{1,2},{1,2,3}}
    84: {{1,2},{1,3},{1,2,3}}
   116: {{1,2},{1,3},{2,3},{1,2,3}}
   308: {{1,2},{1,3},{2,3},{1,4}}
   320: {{1,2,3},{1,4}}
   324: {{1,2},{1,2,3},{1,4}}
   340: {{1,2},{1,3},{1,2,3},{1,4}}
   372: {{1,2},{1,3},{2,3},{1,2,3},{1,4}}

A version for multisets and divisors is A355734.
Sorted positions of first appearances in A367912, for sequences A368109.
The unsorted version is A367913.
A048793 lists binary indices, length A000120, sum A029931.
A058891 counts set-systems, covering A003465, connected A323818.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
Cf. A072639, A309326, A326031, A326702, A326749, A326753, A355733, A355744, A367905, A367906, A367911, A368112, A368185.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
c=Table[Length[Union[Sort/@Tuples[bpe/@bpe[n]]]],{n,10000}];
Select[Range[Length[c]],FreeQ[Take[c,#-1],c[[#]]]&]

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}]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A370640 Number of maximal subsets of {1..n} such that it is possible to choose a different binary index of each element.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A327105 BII-numbers of set-systems with minimum degree 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A367917 BII-numbers of set-systems with the same number of edges as covered vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A370639 Number of subsets of {1..n} containing n such that it is possible to choose a different binary index of each element.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A327101 BII-numbers of 2-cut-connected set-systems (cut-connectivity >= 2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A357135 Take the k-th composition in standard order for each part k of the n-th composition in standard order; then concatenate.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A367913 Least number k such that there are exactly n ways to choose a multiset consisting of a binary index of each binary index of k.

Views

Author

Keywords

Comments

Examples

Crossrefs