A283877 -id:A283877 - cp's OEIS frontend

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

1, 2, 9, 195, 63765, 4294780073, 18446744073639513336, 340282366920938463463374607341656713953, 115792089237316195423570985008687907853269984665640564039457583610129753447747

Offset: 0

Gus Wiseman, Dec 05 2023

nonn

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			The a(2) = 9 sets of sets:
  {{}}
  {{},{1}}
  {{},{2}}
  {{},{1,2}}
  {{},{1},{2}}
  {{},{1},{1,2}}
  {{},{2},{1,2}}
  {{1},{2},{1,2}}
  {{},{1},{2},{1,2}}

Wikipedia, Axiom of choice.

The version for simple graphs is A367867, covering A367868.
The complement is counted by A367902, no singletons A367770, ranks A367906.
The version without empty edges is A367903, ranks A367907.
For a unique choice (instead of none) we have A367904, ranks A367908.
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, unlabeled A323819.
A326031 gives weight of the set-system with BII-number n.
Cf. A007716, A083323, A092918, A102896, A283877, A306445, A355739, A355740, A367769, A367862, A367905.

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

a(n) = 2^2^n - A367902(n). - Christian Sievers, Aug 01 2024

a(5)-a(8) from Christian Sievers, Aug 01 2024

A319558 The squarefree dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted without multiplicity. Then a(n) is the number of non-isomorphic multiset partitions of weight n whose squarefree dual is strict (no repeated blocks).

Original entry on oeis.org

1, 1, 3, 7, 21, 55, 169, 496, 1582, 5080, 17073

Offset: 0

Gus Wiseman, Sep 23 2018

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1, a(2) = 3, and a(3) = 7 multiset partitions:
1:    {{1}}
2:   {{1,1}}
    {{1},{1}}
    {{1},{2}}
3:  {{1,1,1}}
   {{1},{1,1}}
   {{1},{2,2}}
   {{2},{1,2}}
  {{1},{1},{1}}
  {{1},{2},{2}}
  {{1},{2},{3}}

Cf. A007716, A007718, A049311, A053419, A056156, A059201, A283877, A316980.

Cf. A319557, A319559, A319560, A319564, A319565, A319566, A319567.

A367904 Number of sets of nonempty subsets of {1..n} with only one possible way to choose a sequence of different vertices of each edge.

Original entry on oeis.org

1, 2, 6, 38, 666, 32282, 3965886, 1165884638, 792920124786, 1220537093266802, 4187268805038970806, 31649452354183112810198, 522319168680465054600480906, 18683388426164284818805590810122, 1439689660962836496648920949576152046, 237746858936806624825195458794266076911118

Offset: 0

Gus Wiseman, Dec 08 2023

nonn

			The set-system Y = {{1},{1,2},{2,3}} has choices (1,1,2), (1,1,3), (1,2,2), (1,2,3), of which only (1,2,3) has all different elements, so Y is counted under a(3).
The a(0) = 1 through a(2) = 6 set-systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{2}}
             {{1},{2}}
             {{1},{1,2}}
             {{2},{1,2}}

Christian Sievers, Table of n, a(n) for n = 0..77

The maximal case (n subsets) is A003024.
The version for at least one choice is A367902.
The version for no choices is A367903, no singletons A367769, ranks A367907.
These set-systems have ranks A367908, nonzero A367906.
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, unlabeled A323819.
Cf. A102896, A133686, A283877, A306445, A355741, A367770, A367862, A367869, A367901, A367905.

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

a(n) = A367902(n) - A367772(n). - Christian Sievers, Jul 26 2024

Binomial transform of A003024. - Christian Sievers, Aug 12 2024

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

More terms from Christian Sievers, Aug 12 2024

A318099 Number of non-isomorphic weight-n antichains of (not necessarily distinct) multisets whose dual is also an antichain of (not necessarily distinct) multisets.

Original entry on oeis.org

1, 1, 4, 7, 19, 32, 81, 142, 337, 659, 1564

Offset: 0

Gus Wiseman, Sep 25 2018

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,2}} is {{1},{1,2,2}}.

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(3) = 7 antichains:
1: {{1}}
2: {{1,1}}
   {{1,2}}
   {{1},{1}}
   {{1},{2}}
3: {{1,1,1}}
   {{1,2,3}}
   {{1},{2,2}}
   {{1},{2,3}}
   {{1},{1},{1}}
   {{1},{2},{2}}
   {{1},{2},{3}}

Cf. A000219, A006126, A007716, A049311, A059201, A283877, A306007, A316980, A316983, A319558, A319560, A319616-A319646, A300913.

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

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Dec 24 2023

A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements.

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

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

For labeled graphs we have A133686, complement A367867.
For unlabeled graphs we have A134964, complement A140637.
For set-systems we have A367902, complement A367903.
These set-systems have BII-numbers A367906, complement A367907.
The complement is A368094, connected A368409.
Repeats allowed: A368098, ranks A368100, complement A368097, ranks A355529.
Minimal multiset partitions not of this type are counted by A368187.
The connected case is A368410.
Factorizations of this type are counted by A368414, complement A368413.
Allowing repeated edges gives A368422, complement A368421.
A000110 counts set-partitions, non-isomorphic A000041.
A003465 counts covering set-systems, unlabeled A055621.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A001055, A007717, A302545, A306005, A316983, A319560, A321194, A321405, A330223, A367769, A367901.

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

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

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Dec 25 2023

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

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

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

Wikipedia, Axiom of choice.

The case of labeled graphs is A133686, complement A367867.
The case of unlabeled graphs is A134964, complement A140637 (apparently).
Set-systems of this type are A367902, ranks A367906, connected A368410.
The complimentary set-systems are A367903, ranks A367907, connected A368409.
For set-systems we have A368095, complement A368094.
The complement is A368097, ranks A355529.
These multiset partitions have ranks A368100.
The connected case is A368412, complement A368411.
Factorizations of this type are counted by A368414, complement A368413.
For set multipartitions we have A368422, complement A368421.
A000110 counts set partitions, non-isomorphic A000041.
A003465 counts covering set-systems, unlabeled A055621.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A302545, A306005, A316983, A317533, A319616, A330223, A330227, A368187.

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

A319557 Number of non-isomorphic strict connected multiset partitions of weight n.

Original entry on oeis.org

1, 1, 2, 5, 12, 30, 91, 256, 823, 2656, 9103, 31876, 116113, 432824, 1659692, 6508521, 26112327, 106927561, 446654187, 1900858001, 8236367607, 36306790636, 162724173883, 741105774720, 3428164417401, 16099059101049, 76722208278328, 370903316203353, 1818316254655097

Offset: 0

Gus Wiseman, Sep 23 2018

nonn

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

Also the number of non-isomorphic connected T_0 multiset partitions of weight n. In a multiset partition, two vertices are equivalent if in every block the multiplicity of the first is equal to the multiplicity of the second. The T_0 condition means that there are no equivalent vertices.

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

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

Cf. A007716, A007718, A049311, A056156, A283877, A316980.

Cf. A319558, A319559, A319560, A319564, A319565, A319566, A319567.

Inverse Euler transform of A316980.

Terms a(11) and beyond from Andrew Howroyd, Jan 19 2023

A319752 Number of non-isomorphic intersecting multiset partitions of weight n.

Original entry on oeis.org

1, 1, 3, 6, 16, 35, 94, 222, 584, 1488, 3977

Offset: 0

Gus Wiseman, Sep 27 2018

A multiset partition is intersecting if no two parts are disjoint. The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

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

Cf. A007716, A049311, A283877, A305854, A306006, A316980, A319616.

Cf. A319755, A319759, A319760, A319765, A319779, A319787, A319789.

A101370 Number of zero-one matrices with n ones and no zero rows or columns.

Original entry on oeis.org

1, 4, 24, 196, 2016, 24976, 361792, 5997872, 111969552, 2324081728, 53089540992, 1323476327488, 35752797376128, 1040367629940352, 32441861122796672, 1079239231677587264, 38151510015777089280, 1428149538870997774080, 56435732691153773665280

Offset: 1

Peter J. Cameron, Jan 14 2005

a(n) = (1/(4*n!)) * Sum_{r, s>=0} (r*s)_n / 2^(r+s), where (m)_n is the falling factorial m * (m-1) * ... * (m-n+1). [Maia and Mendez]

			a(2)=4:
[1 1] [1] [1 0] [0 1]
..... [1] [0 1] [1 0]
From _Gus Wiseman_, Nov 14 2018: (Start)
The a(3) = 24 matrices:
  [111]
.
  [11][11][110][101][10][100][011][01][010][001]
  [10][01][001][010][11][011][100][11][101][110]
.
  [1][10][10][10][100][100][01][01][010][01][010][001][001]
  [1][10][01][01][010][001][10][10][100][01][001][100][010]
  [1][01][10][01][001][010][10][01][001][10][100][010][100]
(End)

Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, p. 435 (IV, 4. Mitteilungen zur Lehre vom Transfiniten, VIII Nr. 13), Springer, Berlin. [Rainer Rosenthal, Apr 10 2007]

Alois P. Heinz, Table of n, a(n) for n = 1..400
P. J. Cameron, D. A. Gewurz and F. Merola, Product action, Discrete Math., 308 (2008), 386-394.
Giulio Cerbai and Anders Claesson, Enumerative aspects of Caylerian polynomials, arXiv:2411.08426 [math.CO], 2024. See pp. 3, 19.
Loïc Foissy, Claudia Malvenuto, and Frédéric Patras, Matrix symmetric and quasi-symmetric functions and noncommutative representation theory, arXiv:2503.14417 [math.CO], 2025. See p. 20.
M. Maia and M. Mendez, On the arithmetic product of combinatorial species, arXiv:math/0503436 [math.CO], 2005.

Cf. A000670 (the sequence P(n)), A049311 (row and column permutations allowed), A120733, A122725, A135589, A283877, A321446, A321587.

P:=function(n) return Sum([1..n],x->Stirling2(n,x)*Factorial(x)); end;

F:=function(n) return Sum([1..n],x->(-1)^(n-x)*Stirling1(n,x)*P(x)^2)/Factorial(n); end;

m = 17; a670[n_] = Sum[ StirlingS2[n, k]*k!, {k, 0, n}]; Rest[ CoefficientList[ Series[ Sum[ a670[n]^2*(Log[1 + x]^n/n!), {n, 0, m}], {x, 0, m}], x]] (* Jean-François Alcover, Sep 02 2011, after g.f.  *)
Table[Length[Select[Subsets[Tuples[Range[n],2],{n}],And[Union[First/@#]==Range[Max@@First/@#],Union[Last/@#]==Range[Max@@Last/@#]]&]],{n,5}] (* Gus Wiseman, Nov 14 2018 *)

{A000670(n)=sum(k=0,n,stirling(n, k,2)*k!)}
{a(n)=polcoeff(sum(m=0,n,A000670(m)^2*log(1+x+x*O(x^n))^m/m!),n)}
/* Paul D. Hanna, Nov 07 2009 */

a(n) = (Sum s(n, k) * P(k)^2)/n!, where P(n) is the number of labeled total preorders on {1, ..., n} (A000670), s are signed Stirling numbers of the first kind.
G.f.: Sum_{m>=0,n>=0} Sum_{j=0..n} (-1)^(n-j)*binomial(n,j)*((1+x)^j-1)^m. - Vladeta Jovovic, Mar 25 2006
Inverse binomial transform of A007322. - Vladeta Jovovic, Aug 17 2006
G.f.: Sum_{n>=0} 1/(2-(1+x)^n)/2^(n+1). - Vladeta Jovovic, Sep 23 2006
G.f.: Sum_{n>=0} A000670(n)^2*log(1+x)^n/n! where 1/(1-x) = Sum_{n>=0} A000670(n)*log(1+x)^n/n!. - Paul D. Hanna, Nov 07 2009
a(n) ~ n! / (2^(2+log(2)/2) * (log(2))^(2*(n+1))). - Vaclav Kotesovec, Dec 31 2013

A306006 Number of non-isomorphic intersecting set-systems of weight n.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 10, 16, 30, 57, 109, 209, 431, 873, 1850, 3979, 8819, 19863

Offset: 0

Gus Wiseman, Jun 16 2018

An intersecting set-system S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection. The weight of S is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

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

Cf. A007716, A034691, A048143, A049311, A116540, A283877, A293606, A293607, A304867, A305999, A305854-A305857, A306005-A306008.

a(10)-a(17) from Bert Dobbelaere, May 04 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

Views

Author

Keywords

Comments

Examples

Crossrefs

A367904 Number of sets of nonempty subsets of {1..n} with only one possible way to choose a sequence of different vertices of each edge.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A318099 Number of non-isomorphic weight-n antichains of (not necessarily distinct) multisets whose dual is also an antichain of (not necessarily distinct) multisets.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A319557 Number of non-isomorphic strict connected multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A319752 Number of non-isomorphic intersecting multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A101370 Number of zero-one matrices with n ones and no zero rows or columns.

Views

Author

Keywords

Comments

Examples

References