A055621 -id:A055621 - cp's OEIS frontend

A136556 a(n) = binomial(2^n - 1, n).

1, 1, 3, 35, 1365, 169911, 67945521, 89356415775, 396861704798625, 6098989894499557055, 331001552386330913728641, 64483955378425999076128999167, 45677647585984911164223317311276545, 118839819203635450208125966070067352769535, 1144686912178270649701033287538093722740144666625

Offset: 0

Paul D. Hanna, Jan 07 2008; Paul Hanna and Vladeta Jovovic, Jan 15 2008

nonn

Number of n x n binary matrices without zero rows and with distinct rows up to permutation of rows, cf. A014070.
Row 0 of square array A136555.
From Gus Wiseman, Dec 19 2023: (Start)
Also the number of n-element sets of nonempty subsets of {1..n}, or set-systems with n vertices and n edges (not necessarily covering). The covering case is A054780. For example, the a(3) = 35 set-systems are:
  {1}{2}{3}  {1}{2}{12}  {1}{2}{123}  {1}{12}{123}  {12}{13}{123}
             {1}{2}{13}  {1}{3}{123}  {1}{13}{123}  {12}{23}{123}
             {1}{2}{23}  {1}{12}{13}  {1}{23}{123}  {13}{23}{123}
             {1}{3}{12}  {1}{12}{23}  {2}{12}{123}
             {1}{3}{13}  {1}{13}{23}  {2}{13}{123}
             {1}{3}{23}  {2}{3}{123}  {2}{23}{123}
             {2}{3}{12}  {2}{12}{13}  {3}{12}{123}
             {2}{3}{13}  {2}{12}{23}  {3}{13}{123}
             {2}{3}{23}  {2}{13}{23}  {3}{23}{123}
                         {3}{12}{13}  {12}{13}{23}
                         {3}{12}{23}
                         {3}{13}{23}
Of these, only {{1},{2},{1,2}}, {{1},{3},{1,3}}, and {{2},{3},{2,3}} do not cover the vertex set.
(End)

			G.f.: A(x) = 1 + x + 3*x^2 + 35*x^3 + 1365*x^4 + 169911*x^5 +...
A(x) = 1/(1+x) + log(1+2*x)/(1+2*x) + log(1+4*x)^2/(2!*(1+4*x)) + log(1+8*x)^3/(3!*(1+8*x)) + log(1+16*x)^4/(4!*(1+16*x)) + log(1+32*x)^5/(5!*(1+32*x)) +...

G. C. Greubel, Table of n, a(n) for n = 0..50

Sequences of the form binomial(2^n +p*n +q, n): this sequence (0,-1), A014070 (0,0), A136505 (0,1), A136506 (0,2), A060690 (1,-1), A132683 (1,0), A132684 (1,1), A132685 (2,0), A132686 (2,1), A132687 (3,-1), A132688 (3,0), A132689 (3,1).
Cf. A066384, A136555, A136557.
The covering case A054780 has binomial transform A367916, ranks A367917.
Connected graphs of this type are A057500, unlabeled A001429.
Graphs of this type are A116508, covering A367863, unlabeled A006649.
A003465 counts set-systems covering {1..n}, unlabeled A055621.
A058891 counts set-systems, connected A323818, without singletons A016031.
Cf. A055154, A059201, A133686, A367862, A367902, A367903.

[Binomial(2^n -1, n): n in [0..20]]; // G. C. Greubel, Mar 14 2021

A136556:= n-> binomial(2^n-1,n); seq(A136556(n), n=0..20); # G. C. Greubel, Mar 14 2021

f[n_] := Binomial[2^n - 1, n]; Array[f, 12] (* Robert G. Wilson v *)
Table[Length[Subsets[Rest[Subsets[Range[n]]],{n}]],{n,0,4}] (* Gus Wiseman, Dec 19 2023 *)

{a(n) = binomial(2^n-1,n)}
for(n=0, 20, print1(a(n), ", "))

/* As coefficient of x^n in the g.f.: */
{a(n) = polcoeff( sum(i=0,n, 1/(1 + 2^i*x +x*O(x^n)) * log(1 + 2^i*x +x*O(x^n))^i/i!), n)}
for(n=0, 20, print1(a(n), ", "))

from math import comb
def A136556(n): return comb((1<Chai Wah Wu, Jan 02 2024

[binomial(2^n -1, n) for n in (0..20)] # G. C. Greubel, Mar 14 2021

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(2^n,k).
a(n) = (1/n!)*Sum_{k=0..n} Stirling1(n,k) * (2^n-1)^k.
G.f.: Sum_{n>=0} log(1 + 2^n*x)^n / (n! * (1 + 2^n*x)).
a(n) ~ 2^(n^2)/n!. - Vaclav Kotesovec, Jul 02 2016

Edited by N. J. A. Sloane, Jan 26 2008

A367769 Number of finite sets of nonempty non-singleton subsets of {1..n} contradicting a strict version of the axiom of choice.

Original entry on oeis.org

0, 0, 0, 1, 1490, 67027582, 144115188036455750, 1329227995784915872903806998967001298, 226156424291633194186662080095093570025917938800079226639565284090686126876

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.

Includes all set-systems with more edges than covered vertices, but this condition is not sufficient.

			The a(3) = 1 set-system is: {{1,2},{1,3},{2,3},{1,2,3}}.

Wikipedia, Axiom of choice.

Set-systems without singletons are counted by A016031, covering A323816.
The complement is A367770, with singletons allowed A367902 (ranks A367906).
The version for simple graphs is A367867, covering A367868.
The version allowing singletons and empty edges is A367901.
The version allowing singletons is A367903, ranks A367907.
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.
Cf. A007716, A092918, A102896, A283877, A306445, A326031, A355739, A355740, A355741, A367904, A367905.

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

a(n) = 2^(2^n-n-1) - A367770(n) = A016031(n+1) - A367770(n). - Christian Sievers, Jul 28 2024

a(6)-a(8) from Christian Sievers, Jul 28 2024

A330060 MM-numbers of VDD-normalized multisets of multisets.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 15, 16, 18, 19, 21, 24, 26, 27, 28, 30, 32, 35, 36, 37, 38, 39, 42, 45, 48, 49, 52, 53, 54, 56, 57, 60, 63, 64, 70, 72, 74, 76, 78, 81, 84, 89, 90, 91, 95, 96, 98, 104, 105, 106, 108, 111, 112, 113, 114, 117, 120, 126, 128

Offset: 1

Gus Wiseman, Dec 03 2019

First differs from A330104 and A330120 in having 35 and lacking 69, with corresponding multisets of multisets 35: {{2},{1,1}} and 69: {{1},{2,2}}.
First differs from A330108 in having 207 and lacking 175, with corresponding multisets of multisets 207: {{1},{1},{2,2}} and 175: {{2},{2},{1,1}}.
We define the VDD (vertex-degrees decreasing) normalization of a multiset of multisets 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 is first by length and then lexicographically.
For example, 15301 is the MM-number of {{3},{1,2},{1,1,4}}, which has the following normalizations together with their MM-numbers:
  Brute-force:    43287: {{1},{2,3},{2,2,4}}
  Lexicographic:  43143: {{1},{2,4},{2,2,3}}
  VDD:            15515: {{2},{1,3},{1,1,4}}
  MM:             15265: {{2},{1,4},{1,1,3}}
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset of multisets with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset of multisets with MM-number 78 is {{},{1},{1,2}}.

			The sequence of all VDD-normalized multisets of multisets together with their MM-numbers begins:
   1: 0           21: {1}{11}        49: {11}{11}         84: {}{}{1}{11}
   2: {}          24: {}{}{}{1}      52: {}{}{12}         89: {1112}
   3: {1}         26: {}{12}         53: {1111}           90: {}{1}{1}{2}
   4: {}{}        27: {1}{1}{1}      54: {}{1}{1}{1}      91: {11}{12}
   6: {}{1}       28: {}{}{11}       56: {}{}{}{11}       95: {2}{111}
   7: {11}        30: {}{1}{2}       57: {1}{111}         96: {}{}{}{}{}{1}
   8: {}{}{}      32: {}{}{}{}{}     60: {}{}{1}{2}       98: {}{11}{11}
   9: {1}{1}      35: {2}{11}        63: {1}{1}{11}      104: {}{}{}{12}
  12: {}{}{1}     36: {}{}{1}{1}     64: {}{}{}{}{}{}    105: {1}{2}{11}
  13: {12}        37: {112}          70: {}{2}{11}       106: {}{1111}
  14: {}{11}      38: {}{111}        72: {}{}{}{1}{1}    108: {}{}{1}{1}{1}
  15: {1}{2}      39: {1}{12}        74: {}{112}         111: {1}{112}
  16: {}{}{}{}    42: {}{1}{11}      76: {}{}{111}       112: {}{}{}{}{11}
  18: {}{1}{1}    45: {1}{1}{2}      78: {}{1}{12}       113: {123}
  19: {111}       48: {}{}{}{}{1}    81: {1}{1}{1}{1}    114: {}{1}{111}

Equals the image/fixed points of the idempotent sequence A330061.
A subset of A320456.
Non-isomorphic multiset partitions are A007716.
MM-weight is A302242.
Cf. A000612, A055621, A056239, A112798, A283877, A316983, A317533, A330098, A330102, A330103, 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).

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
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[100],Sort[primeMS/@primeMS[#]]==sysnorm[primeMS/@primeMS[#]]&]

A330097 MM-numbers of VDD-normalized multiset partitions.

Original entry on oeis.org

1, 3, 7, 9, 13, 15, 19, 21, 27, 35, 37, 39, 45, 49, 53, 57, 63, 81, 89, 91, 95, 105, 111, 113, 117, 131, 133, 135, 141, 147, 151, 159, 161, 165, 169, 171, 183, 189, 195, 207, 223, 225, 243, 245, 247, 259, 265, 267, 273, 281, 285, 311, 315, 329, 333, 339, 343

Offset: 1

Gus Wiseman, Dec 04 2019

nonn

First differs from A330122 in having 207 and lacking 175, with corresponding multiset partitions 207: {{1},{1},{2,2}} and 175: {{2},{2},{1,1}}.
A multiset partition is a finite multiset of finite nonempty multisets of positive integers.
We define the VDD (vertex-degrees decreasing) normalization of a multiset of multisets 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 multisets is first by length and then lexicographically.
For example, 15301 is the MM-number of {{3},{1,2},{1,1,4}}, which has the following normalizations together with their MM-numbers:
  Brute-force:    43287: {{1},{2,3},{2,2,4}}
  Lexicographic:  43143: {{1},{2,4},{2,2,3}}
  VDD:            15515: {{2},{1,3},{1,1,4}}
  MM:             15265: {{2},{1,4},{1,1,3}}
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset of multisets with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset of multisets with MM-number 78 is {{},{1},{1,2}}.

			The sequence of all VDD-normalized multiset partitions together with their MM-numbers begins:
   1: 0             57: {1}{111}        151: {1122}
   3: {1}           63: {1}{1}{11}      159: {1}{1111}
   7: {11}          81: {1}{1}{1}{1}    161: {11}{22}
   9: {1}{1}        89: {1112}          165: {1}{2}{3}
  13: {12}          91: {11}{12}        169: {12}{12}
  15: {1}{2}        95: {2}{111}        171: {1}{1}{111}
  19: {111}        105: {1}{2}{11}      183: {1}{122}
  21: {1}{11}      111: {1}{112}        189: {1}{1}{1}{11}
  27: {1}{1}{1}    113: {123}           195: {1}{2}{12}
  35: {2}{11}      117: {1}{1}{12}      207: {1}{1}{22}
  37: {112}        131: {11111}         223: {11112}
  39: {1}{12}      133: {11}{111}       225: {1}{1}{2}{2}
  45: {1}{1}{2}    135: {1}{1}{1}{2}    243: {1}{1}{1}{1}{1}
  49: {11}{11}     141: {1}{23}         245: {2}{11}{11}
  53: {1111}       147: {1}{11}{11}     247: {12}{111}
For example, 1155 is the MM-number of {{1},{2},{3},{1,1}}, which is VDD-normalized, so 1155 belongs to the sequence.
On the other hand, 69  is the MM-number of {{1},{2,2}}, but the VDD-normalization is {{2},{1,1}}, so 69 does not belong to the sequence.

Equals the odd terms of A330060.
A subset of A320634.
Non-isomorphic multiset partitions are A007716.
MM-weight is A302242.
Cf. A000612, A055621, A056239, A112798, A283877, A316983, A317533, A320456, A330061, A330098, A330102, A330103, 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).

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
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[1,100,2],Sort[primeMS/@primeMS[#]]==sysnorm[primeMS/@primeMS[#]]&]

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[#]]&]

A330104 MM-numbers of brute-force normalized multisets of multisets.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 15, 16, 18, 19, 21, 24, 26, 27, 28, 30, 32, 36, 37, 38, 39, 42, 45, 48, 49, 52, 53, 54, 56, 57, 60, 63, 64, 69, 72, 74, 76, 78, 81, 84, 89, 90, 91, 96, 98, 104, 105, 106, 108, 111, 112, 113, 114, 117, 120, 126, 128, 131, 133

Offset: 1

Gus Wiseman, Dec 02 2019

First differs from A330060 and A330108 in having 69 and lacking 35, with corresponding multisets of multisets 69: {{1},{2,2}} and 35: {{2},{1,1}}.
First differs from A330120 in having 435 and lacking 429, with corresponding multisets of multisets 435: {{1},{2},{1,3}} and 429: {{1},{3},{1,2}}.
We define the brute-force normalization of a multiset of multisets 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 multisets is first by length and then lexicographically.
For example, 15301 is the MM-number of {{3},{1,2},{1,1,4}}, which has the following normalizations together with their MM-numbers:
  Brute-force:    43287: {{1},{2,3},{2,2,4}}
  Lexicographic:  43143: {{1},{2,4},{2,2,3}}
  VDD:            15515: {{2},{1,3},{1,1,4}}
  MM:             15265: {{2},{1,4},{1,1,3}}
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset of multisets with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset of multisets with MM-number 78 is {{},{1},{1,2}}.

			The sequence of all brute-force normalized multisets of multisets together with their MM-numbers begins:
   1: 0           21: {1}{11}        52: {}{}{12}         89: {1112}
   2: {}          24: {}{}{}{1}      53: {1111}           90: {}{1}{1}{2}
   3: {1}         26: {}{12}         54: {}{1}{1}{1}      91: {11}{12}
   4: {}{}        27: {1}{1}{1}      56: {}{}{}{11}       96: {}{}{}{}{}{1}
   6: {}{1}       28: {}{}{11}       57: {1}{111}         98: {}{11}{11}
   7: {11}        30: {}{1}{2}       60: {}{}{1}{2}      104: {}{}{}{12}
   8: {}{}{}      32: {}{}{}{}{}     63: {1}{1}{11}      105: {1}{2}{11}
   9: {1}{1}      36: {}{}{1}{1}     64: {}{}{}{}{}{}    106: {}{1111}
  12: {}{}{1}     37: {112}          69: {1}{22}         108: {}{}{1}{1}{1}
  13: {12}        38: {}{111}        72: {}{}{}{1}{1}    111: {1}{112}
  14: {}{11}      39: {1}{12}        74: {}{112}         112: {}{}{}{}{11}
  15: {1}{2}      42: {}{1}{11}      76: {}{}{111}       113: {123}
  16: {}{}{}{}    45: {1}{1}{2}      78: {}{1}{12}       114: {}{1}{111}
  18: {}{1}{1}    48: {}{}{}{}{1}    81: {1}{1}{1}{1}    117: {1}{1}{12}
  19: {111}       49: {11}{11}       84: {}{}{1}{11}     120: {}{}{}{1}{2}

Equals the image/fixed points of the idempotent sequence A330105.
Non-isomorphic multiset partitions are A007716.
Cf. A000612, A055621, A283877, A316983, A317533, A330098, A330101, A330103.
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).

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
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[100],Sort[primeMS/@primeMS[#]]==brute[primeMS/@primeMS[#]]&]

A330107 MM-numbers of brute-force normalized multiset partitions.

Original entry on oeis.org

1, 3, 7, 9, 13, 15, 19, 21, 27, 37, 39, 45, 49, 53, 57, 63, 69, 81, 89, 91, 105, 111, 113, 117, 131, 133, 135, 141, 147, 151, 159, 161, 165, 169, 171, 183, 189, 195, 207, 223, 225, 243, 247, 259, 267, 273, 281, 285, 309, 311, 315, 329, 333, 339, 343, 351, 359

Offset: 1

Gus Wiseman, Dec 02 2019

A multiset partition is a finite multiset of finite nonempty multisets of positive integers.
We define the brute-force normalization of a multiset of multisets 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 multisets is first by length and then lexicographically.
For example, 15301 is the MM-number of {{3},{1,2},{1,1,4}}, which has the following normalizations together with their MM-numbers:
  Brute-force:    43287: {{1},{2,3},{2,2,4}}
  Lexicographic:  43143: {{1},{2,4},{2,2,3}}
  VDD:            15515: {{2},{1,3},{1,1,4}}
  MM:             15265: {{2},{1,4},{1,1,3}}
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset of multisets with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset of multisets with MM-number 78 is {{},{1},{1,2}}.

			The sequence of all brute-force normalized multiset partitions together with their MM-numbers begins:
   1: 0             63: {1}{1}{11}      159: {1}{1111}
   3: {1}           69: {1}{22}         161: {11}{22}
   7: {11}          81: {1}{1}{1}{1}    165: {1}{2}{3}
   9: {1}{1}        89: {1112}          169: {12}{12}
  13: {12}          91: {11}{12}        171: {1}{1}{111}
  15: {1}{2}       105: {1}{2}{11}      183: {1}{122}
  19: {111}        111: {1}{112}        189: {1}{1}{1}{11}
  21: {1}{11}      113: {123}           195: {1}{2}{12}
  27: {1}{1}{1}    117: {1}{1}{12}      207: {1}{1}{22}
  37: {112}        131: {11111}         223: {11112}
  39: {1}{12}      133: {11}{111}       225: {1}{1}{2}{2}
  45: {1}{1}{2}    135: {1}{1}{1}{2}    243: {1}{1}{1}{1}{1}
  49: {11}{11}     141: {1}{23}         247: {12}{111}
  53: {1111}       147: {1}{11}{11}     259: {11}{112}
  57: {1}{111}     151: {1122}          267: {1}{1112}

Equals the odd terms of A330104.
Non-isomorphic multiset partitions are A007716.
Cf. A000612, A055621, A283877, A300300, A316983, A317533, A320664, A330061, A330098, A330101, A330103, 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).

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
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[1,100,2],Sort[primeMS/@primeMS[#]]==brute[primeMS/@primeMS[#]]&]

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[#]]&]

A330110 BII-numbers of lexicographically normalized set-systems.

Original entry on oeis.org

0, 1, 3, 4, 5, 7, 11, 13, 15, 20, 21, 23, 31, 33, 37, 45, 52, 53, 55, 63, 64, 65, 67, 68, 69, 71, 75, 77, 79, 84, 85, 87, 95, 97, 101, 109, 116, 117, 119, 127, 139, 141, 143, 149, 151, 159, 165, 173, 181, 183, 191, 193, 195, 197, 199, 203, 205, 207, 213, 215

Offset: 1

Gus Wiseman, Dec 05 2019

nonn

First differs from A330099 in having 13 and lacking 19.
First differs from A330123 in having 141 and lacking 180, with corresponding set-systems 141: {{1},{3},{4},{1,2}} and 180: {{4},{1,2},{1,3},{2,3}}.
We define the lexicographic normalization of a multiset of multisets 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 lexicographically least of these representatives.
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.
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 lexicographically 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}
  13: {1}{3}{12}           67: {1}{2}{123}
  15: {1}{2}{3}{12}        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}    77: {1}{3}{12}{123}
  33: {1}{23}              79: {1}{2}{3}{12}{123}
  37: {1}{12}{23}          84: {12}{13}{123}
  45: {1}{3}{12}{23}       85: {1}{12}{13}{123}

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, A330101, A330102, A330194, A330195.
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).

cp's OEIS Frontend

A136556 a(n) = binomial(2^n - 1, n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A367769 Number of finite sets of nonempty non-singleton subsets of {1..n} contradicting a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A330060 MM-numbers of VDD-normalized multisets of multisets.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330097 MM-numbers of VDD-normalized multiset partitions.

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

A330104 MM-numbers of brute-force normalized multisets of multisets.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A330107 MM-numbers of brute-force normalized multiset partitions.

Views

Author

Keywords