A321405 -id:A321405 - cp's OEIS frontend

A138178 Number of symmetric matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n.

1, 1, 3, 9, 33, 125, 531, 2349, 11205, 55589, 291423, 1583485, 8985813, 52661609, 319898103, 2000390153, 12898434825, 85374842121, 580479540219, 4041838056561, 28824970996809, 210092964771637, 1564766851282299, 11890096357039749, 92151199272181629

Offset: 0

Vladeta Jovovic, Mar 03 2008

Number of normal semistandard Young tableaux of size n, where a tableau is normal if its entries span an initial interval of positive integers. - Gus Wiseman, Feb 23 2018

			a(4) = 33 because there are 1 such matrix of type 1 X 1, 7 matrices of type 2 X 2, 15 of type 3 X 3 and 10 of type 4 X 4, cf. A138177.
From _Gus Wiseman_, Feb 23 2018: (Start)
The a(3) = 9 normal semistandard Young tableaux:
1   1 2   1 3   1 2   1 1   1 2 3   1 2 2   1 1 2   1 1 1
2   3     2     2     2
3
(End)
From _Gus Wiseman_, Nov 14 2018: (Start)
The a(4) = 33 matrices:
[4]
.
[30][21][20][11][10][02][01]
[01][10][02][11][03][20][12]
.
[200][200][110][101][100][100][100][100][011][010][010][010][001][001][001]
[010][001][100][010][020][011][010][001][100][110][101][100][020][010][001]
[001][010][001][100][001][010][002][011][100][001][010][002][100][101][110]
.
[1000][1000][1000][1000][0100][0100][0010][0010][0001][0001]
[0100][0100][0010][0001][1000][1000][0100][0001][0100][0010]
[0010][0001][0100][0010][0010][0001][1000][1000][0010][0100]
[0001][0010][0001][0100][0001][0010][0001][0100][1000][1000]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..500

Row sums of A138177.
Cf. A007716, A120733, A135588, A296188.
Cf. A057151, A104601, A104602, A120732, A316983, A320796, A321401, A321405, A321407.

gf:= proc(j) local k, n; add(add((-1)^(n-k) *binomial(n, k) *(1-x)^(-k) *(1-x^2)^(-binomial(k, 2)), k=0..n), n=0..j) end: a:= n-> coeftayl(gf(n+1), x=0, n): seq(a(n), n=0..25); # Alois P. Heinz, Sep 25 2008

Table[Sum[SeriesCoefficient[1/(2^(k+1)*(1-x)^k*(1-x^2)^(k*(k-1)/2)),{x,0,n}],{k,0,Infinity}],{n,0,20}]  (* Vaclav Kotesovec, Jul 03 2014 *)
multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]]; Table[Length[Select[multsubs[Tuples[Range[n],2],n],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#],Sort[Reverse/@#]==#]&]],{n,5}] (* Gus Wiseman, Nov 14 2018 *)

G.f.: Sum_{n>=0} Sum_{k=0..n} (-1)^(n-k)*C(n,k)*(1-x)^(-k)*(1-x^2)^(-C(k,2)).

G.f.: Sum_{n>=0} 2^(-n-1)*(1-x)^(-n)*(1-x^2)^(-C(n,2)). - Vladeta Jovovic, Dec 09 2009

More terms from Alois P. Heinz, Sep 25 2008

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

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

A367862 Number of n-vertex labeled simple graphs with the same number of edges as covered vertices.

Original entry on oeis.org

1, 1, 1, 2, 20, 308, 5338, 105298, 2366704, 60065072, 1702900574, 53400243419, 1836274300504, 68730359299960, 2782263907231153, 121137565273808792, 5645321914669112342, 280401845830658755142, 14788386825536445299398, 825378055206721558026931, 48604149005046792753887416

Offset: 0

Gus Wiseman, Dec 07 2023

nonn

Unlike the connected case (A057500), these graphs may have more than one cycle; for example, the graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}} has multiple cycles.

			Non-isomorphic representatives of the a(4) = 20 graphs:
  {}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,4},{2,3}}
  {{1,2},{1,3},{2,4},{3,4}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

The connected case is A057500, unlabeled A001429.
Counting all vertices (not just covered) gives A116508.
The covering case is A367863, unlabeled A006649.
For set-systems we have A367916, ranks A367917.
A001187 counts connected graphs, A001349 unlabeled.
A003465 counts covering set-systems, unlabeled A055621, ranks A326754.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
A143543 counts simple labeled graphs by number of connected components.
A323818 counts connected set-systems, unlabeled A323819, ranks A326749.
A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
Cf. A006126, A316983, A321405, A326754, A326870, A326877, A367770, A367901, A367902, A367903.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Length[#]==Length[Union@@#]&]],{n,0,5}]

\\ Here b(n) is A367863(n)
b(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(binomial(k,2), n))
a(n) = sum(k=0, n, binomial(n,k) * b(k)) \\ Andrew Howroyd, Dec 29 2023

Binomial transform of A367863.

Terms a(8) and beyond from Andrew Howroyd, Dec 29 2023

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

A330099 BII-numbers of brute-force normalized set-systems.

Original entry on oeis.org

0, 1, 3, 4, 5, 7, 11, 15, 19, 20, 21, 23, 31, 33, 37, 51, 52, 53, 55, 63, 64, 65, 67, 68, 69, 71, 75, 79, 83, 84, 85, 87, 95, 97, 101, 115, 116, 117, 119, 127, 139, 143, 159, 191, 203, 207, 223, 255, 267, 271, 275, 276, 277, 279, 287, 307, 308, 309, 311, 319, 331

Offset: 1

Gus Wiseman, Dec 02 2019

First differs from A330100 in having 545 and lacking 179, with corresponding set-systems 545: {{1},{2,3},{2,4}} and 179: {{1},{2},{4},{1,3},{2,3}}.
A set-system is a finite set of finite nonempty sets of positive integers.
We define the brute-force normalization of a set-system to be obtained by first normalizing so that the vertices cover an initial interval of positive integers, then applying all permutations to the vertex set, and finally taking the least representative, where the ordering of sets is first by length and then lexicographically.
For example, 156 is the BII-number of {{3},{4},{1,2},{1,3}}, which has the following normalizations, together with their BII-numbers:
  Brute-force:    2067: {{1},{2},{1,3},{3,4}}
  Lexicographic:   165: {{1},{4},{1,2},{2,3}}
  VDD:             525: {{1},{3},{1,2},{2,4}}
  MM:              270: {{2},{3},{1,2},{1,4}}
  BII:             150: {{2},{4},{1,2},{1,3}}
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 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.
There are A055621(n) entries m such that A326702(m) = n, where A326702(k) is the number of covered vertices in the set-system with BII-number k.
There are A283877(n) entries m such that A326031(m) = n, where A326031(k) is the weight of the set-system with BII-number k.

			The sequence of all nonempty brute-force normalized set-systems together with their BII-numbers begins:
   1: {1}                  52: {12}{13}{23}
   3: {1}{2}               53: {1}{12}{13}{23}
   4: {12}                 55: {1}{2}{12}{13}{23}
   5: {1}{12}              63: {1}{2}{3}{12}{13}{23}
   7: {1}{2}{12}           64: {123}
  11: {1}{2}{3}            65: {1}{123}
  15: {1}{2}{3}{12}        67: {1}{2}{123}
  19: {1}{2}{13}           68: {12}{123}
  20: {12}{13}             69: {1}{12}{123}
  21: {1}{12}{13}          71: {1}{2}{12}{123}
  23: {1}{2}{12}{13}       75: {1}{2}{3}{123}
  31: {1}{2}{3}{12}{13}    79: {1}{2}{3}{12}{123}
  33: {1}{23}              83: {1}{2}{13}{123}
  37: {1}{12}{23}          84: {12}{13}{123}
  51: {1}{2}{13}{23}       85: {1}{12}{13}{123}

Equals the image/fixed points of the idempotent sequence A330101.
Non-isomorphic multiset partitions are A007716.
Unlabeled spanning set-systems by span are A055621.
Unlabeled spanning set-systems by weight are A283877.
Cf. A000612, A300913, A321405, A330061, A330102, A330105.
Other fixed points:
- Brute-force: A330104 (multisets of multisets), A330107 (multiset partitions), A330099 (set-systems).
- Lexicographic: A330120 (multisets of multisets), A330121 (multiset partitions), A330110 (set-systems).
- VDD: A330060 (multisets of multisets), A330097 (multiset partitions), A330100 (set-systems).
- MM: A330108 (multisets of multisets), A330122 (multiset partitions), A330123 (set-systems).
- BII: A330109 (set-systems).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
brute[m_]:=If[Union@@m!={}&&Union@@m!=Range[Max@@Flatten[m]],brute[m/.Rule@@@Table[{(Union@@m)[[i]],i},{i,Length[Union@@m]}]],First[Sort[brute[m,1]]]];
brute[m_,1]:=Table[Sort[Sort/@(m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])],{p,Permutations[Union@@m]}];
Select[Range[0,100],Sort[bpe/@bpe[#]]==brute[bpe/@bpe[#]]&]

A330100 BII-numbers of VDD-normalized set-systems.

Original entry on oeis.org

0, 1, 3, 4, 5, 7, 11, 15, 19, 20, 21, 23, 31, 33, 37, 51, 52, 53, 55, 63, 64, 65, 67, 68, 69, 71, 75, 79, 83, 84, 85, 87, 95, 97, 101, 115, 116, 117, 119, 127, 139, 143, 159, 179, 180, 181, 183, 191, 203, 207, 211, 212, 213, 215, 223, 225, 229, 243, 244, 245, 247

Offset: 0

Gus Wiseman, Dec 04 2019

First differs from A330099 in lacking 545 and having 179, with corresponding set-systems 545: {{1},{2,3},{2,4}} and 179: {{1},{2},{4},{1,3},{2,3}}.
A set-system is a finite set of finite nonempty sets of positive integers.
We define the VDD (vertex-degrees decreasing) normalization of a set-system to be obtained by first normalizing so that the vertices cover an initial interval of positive integers, then applying all permutations to the vertex set, then selecting only the representatives whose vertex-degrees are weakly decreasing, and finally taking the least of these representatives, where the ordering of sets is first by length and then lexicographically.
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 of positive integers) 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.
For example, 156 is the BII-number of {{3},{4},{1,2},{1,3}}, which has the following normalizations, together with their BII-numbers:
  Brute-force:    2067: {{1},{2},{1,3},{3,4}}
  Lexicographic:   165: {{1},{4},{1,2},{2,3}}
  VDD:             525: {{1},{3},{1,2},{2,4}}
  MM:              270: {{2},{3},{1,2},{1,4}}
  BII:             150: {{2},{4},{1,2},{1,3}}

			The sequence of all nonempty VDD-normalized set-systems together with their BII-numbers begins:
   1: {1}                  52: {12}{13}{23}
   3: {1}{2}               53: {1}{12}{13}{23}
   4: {12}                 55: {1}{2}{12}{13}{23}
   5: {1}{12}              63: {1}{2}{3}{12}{13}{23}
   7: {1}{2}{12}           64: {123}
  11: {1}{2}{3}            65: {1}{123}
  15: {1}{2}{3}{12}        67: {1}{2}{123}
  19: {1}{2}{13}           68: {12}{123}
  20: {12}{13}             69: {1}{12}{123}
  21: {1}{12}{13}          71: {1}{2}{12}{123}
  23: {1}{2}{12}{13}       75: {1}{2}{3}{123}
  31: {1}{2}{3}{12}{13}    79: {1}{2}{3}{12}{123}
  33: {1}{23}              83: {1}{2}{13}{123}
  37: {1}{12}{23}          84: {12}{13}{123}
  51: {1}{2}{13}{23}       85: {1}{12}{13}{123}

Equals the image/fixed points of the idempotent sequence A330102.
A subset of A326754.
Non-isomorphic multiset partitions are A007716.
Unlabeled spanning set-systems counted by vertices are A055621.
Unlabeled set-systems counted by weight are A283877.
Cf. A000120, A000612, A048793, A070939, A300913, A319559, A321405, A326031, A330061, A330101.
Other fixed points:
- Brute-force: A330104 (multisets of multisets), A330107 (multiset partitions), A330099 (set-systems).
- Lexicographic: A330120 (multisets of multisets), A330121 (multiset partitions), A330110 (set-systems).
- VDD: A330060 (multisets of multisets), A330097 (multiset partitions), A330100 (set-systems).
- MM: A330108 (multisets of multisets), A330122 (multiset partitions), A330123 (set-systems).
- BII: A330109 (set-systems).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
sysnorm[m_]:=If[Union@@m!={}&&Union@@m!=Range[Max@@Flatten[m]],sysnorm[m/.Rule@@@Table[{(Union@@m)[[i]],i},{i,Length[Union@@m]}]],First[Sort[sysnorm[m,1]]]];
sysnorm[m_,aft_]:=If[Length[Union@@m]<=aft,{m},With[{mx=Table[Count[m,i,{2}],{i,Select[Union@@m,#>=aft&]}]},Union@@(sysnorm[#,aft+1]&/@Union[Table[Map[Sort,m/.{par+aft-1->aft,aft->par+aft-1},{0,1}],{par,First/@Position[mx,Max[mx]]}]])]];
Select[Range[0,100],Sort[bpe/@bpe[#]]==sysnorm[bpe/@bpe[#]]&]

A330109 BII-numbers of BII-normalized set-systems.

Original entry on oeis.org

0, 1, 3, 4, 5, 7, 11, 12, 13, 15, 20, 21, 22, 23, 30, 31, 52, 53, 55, 63, 64, 65, 67, 68, 69, 71, 75, 76, 77, 79, 84, 85, 86, 87, 94, 95, 116, 117, 119, 127, 139, 140, 141, 143, 148, 149, 150, 151, 158, 159, 180, 181, 183, 191, 192, 193, 195, 196, 197, 199, 203

Offset: 1

Gus Wiseman, Dec 05 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 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.
We define the BII-normalization of a set-system to be obtained by first normalizing so that the vertices cover an initial interval of positive integers, then applying all permutations to the vertex set, and finally taking the representative with the smallest BII-number.
For example, 156 is the BII-number of {{3},{4},{1,2},{1,3}}, which has the following normalizations, together with their BII-numbers:
  Brute-force:    2067: {{1},{2},{1,3},{3,4}}
  Lexicographic:   165: {{1},{4},{1,2},{2,3}}
  VDD:             525: {{1},{3},{1,2},{2,4}}
  MM:              270: {{2},{3},{1,2},{1,4}}
  BII:             150: {{2},{4},{1,2},{1,3}}

			The sequence of all nonempty BII-normalized set-systems together with their BII-numbers begins:
   1: {1}                  52: {12}{13}{23}
   3: {1}{2}               53: {1}{12}{13}{23}
   4: {12}                 55: {1}{2}{12}{13}{23}
   5: {1}{12}              63: {1}{2}{3}{12}{13}{23}
   7: {1}{2}{12}           64: {123}
  11: {1}{2}{3}            65: {1}{123}
  12: {3}{12}              67: {1}{2}{123}
  13: {1}{3}{12}           68: {12}{123}
  15: {1}{2}{3}{12}        69: {1}{12}{123}
  20: {12}{13}             71: {1}{2}{12}{123}
  21: {1}{12}{13}          75: {1}{2}{3}{123}
  22: {2}{12}{13}          76: {3}{12}{123}
  23: {1}{2}{12}{13}       77: {1}{3}{12}{123}
  30: {2}{3}{12}{13}       79: {1}{2}{3}{12}{123}
  31: {1}{2}{3}{12}{13}    84: {12}{13}{123}

Equals the image/fixed points of the idempotent sequence A330195.
A subset of A326754.
Unlabeled covering set-systems counted by vertices are A055621.
Unlabeled set-systems counted by weight are A283877.
BII-weight is A326031.
Cf. A000120, A000612, A048793, A070939, A300913, A319559, A321405, A330101, A330102.
Other fixed points:
- Brute-force: A330104 (multisets of multisets), A330107 (multiset partitions), A330099 (set-systems).
- Lexicographic: A330120 (multisets of multisets), A330121 (multiset partitions), A330110 (set-systems).
- VDD: A330060 (multisets of multisets), A330097 (multiset partitions), A330100 (set-systems).
- MM: A330108 (multisets of multisets), A330122 (multiset partitions), A330123 (set-systems).
- BII: A330109 (set-systems).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
fbi[q_]:=If[q=={},0,Total[2^q]/2];
biinorm[m_]:=If[Union@@m!={}&&Union@@m!=Range[Max@@Flatten[m]],biinorm[m/.Rule@@@Table[{(Union@@m)[[i]],i},{i,Length[Union@@m]}]],First[SortBy[brute[m,1],fbi[fbi/@#]&]]];
brute[m_,1]:=Table[Sort[Sort/@(m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])],{p,Permutations[Union@@m]}];
Select[Range[0,100],Sort[bpe/@bpe[#]]==biinorm[bpe/@bpe[#]]&]

A330101 BII-number of the brute-force normalization of the set-system with BII-number n.

Original entry on oeis.org

0, 1, 1, 3, 4, 5, 5, 7, 1, 3, 3, 11, 33, 19, 19, 15, 4, 5, 33, 19, 20, 21, 37, 23, 5, 7, 19, 15, 37, 23, 51, 31, 4, 33, 5, 19, 20, 37, 21, 23, 5, 19, 7, 15, 37, 51, 23, 31, 20, 37, 37, 51, 52, 53, 53, 55, 21, 23, 23, 31, 53, 55, 55, 63, 64, 65, 65, 67, 68, 69, 69

Offset: 0

Gus Wiseman, Dec 02 2019

nonn

First differs from A330102 at a(148) = 545, A330102(148) = 274, with corresponding set-systems 545: {{1},{2,3},{2,4}} and 274: {{2},{1,3},{1,4}}.
A set-system is a finite set of finite nonempty sets of positive integers.
We define the brute-force normalization of a set-system to be obtained by first normalizing so that the vertices cover an initial interval of positive integers, then applying all permutations to the vertex set, and finally taking the least representative, where the ordering of sets is first by length and then lexicographically.
For example, 156 is the BII-number of {{3},{4},{1,2},{1,3}}, which has the following normalizations, together with their BII-numbers:
  Brute-force:    2067: {{1},{2},{1,3},{3,4}}
  Lexicographic:   165: {{1},{4},{1,2},{2,3}}
  VDD:             525: {{1},{3},{1,2},{2,4}}
  MM:              270: {{2},{3},{1,2},{1,4}}
  BII:             150: {{2},{4},{1,2},{1,3}}
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 of positive integers) 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.

Wikipedia, Idempotence

This sequence is idempotent and its image and fixed points are A330099.
Non-isomorphic multiset partitions are A007716.
Unlabeled spanning set-systems by vertices are A055621.
Unlabeled set-systems by weight are A283877.
Cf. A000612, A300913, A321405, A330061, A330102, A330105.
Other fixed points:
- Brute-force: A330104 (multisets of multisets), A330107 (multiset partitions), A330099 (set-systems).
- Lexicographic: A330120 (multisets of multisets), A330121 (multiset partitions), A330110 (set-systems).
- VDD: A330060 (multisets of multisets), A330097 (multiset partitions), A330100 (set-systems).
- MM: A330108 (multisets of multisets), A330122 (multiset partitions), A330123 (set-systems).
- BII: A330109 (set-systems).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
fbi[q_]:=If[q=={},0,Total[2^q]/2];
brute[m_]:=If[Union@@m!={}&&Union@@m!=Range[Max@@Flatten[m]],brute[m/.Rule@@@Table[{(Union@@m)[[i]],i},{i,Length[Union@@m]}]],First[Sort[brute[m,1]]]];
brute[m_,1]:=Table[Sort[Sort/@(m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])],{p,Permutations[Union@@m]}];
Table[fbi[fbi/@brute[bpe/@bpe[n]]],{n,0,100}]

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

Original entry on oeis.org

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

cp's OEIS Frontend

A138178 Number of symmetric matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

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

A367862 Number of n-vertex labeled simple graphs with the same number of edges as covered vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A330099 BII-numbers of brute-force normalized set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330100 BII-numbers of VDD-normalized set-systems.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330109 BII-numbers of BII-normalized set-systems.

Views

Author

Keywords

Comments

Examples