cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-7 of 7 results.

A326970 Number of set-systems covering n vertices whose dual is a weak antichain.

Original entry on oeis.org

1, 1, 3, 43, 19251
Offset: 0

Views

Author

Gus Wiseman, Aug 10 2019

Keywords

Comments

A set-system is a finite set of finite nonempty sets. The dual of a set-system has, for each vertex, one edges consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. A weak antichain is a multiset of sets, none of which is a proper subset of any other.

Examples

			The a(3) = 43 set-systems:
  {123}  {1}{23}  {1}{2}{3}     {1}{2}{3}{12}
         {2}{13}  {12}{13}{23}  {1}{2}{3}{13}
         {3}{12}  {1}{23}{123}  {1}{2}{3}{23}
                  {2}{13}{123}  {1}{2}{13}{23}
                  {3}{12}{123}  {1}{2}{3}{123}
                                {1}{3}{12}{23}
                                {2}{3}{12}{13}
                                {1}{12}{13}{23}
                                {2}{12}{13}{23}
                                {3}{12}{13}{23}
                                {12}{13}{23}{123}
.
  {1}{2}{3}{12}{13}     {1}{2}{3}{12}{13}{23}    {1}{2}{3}{12}{13}{23}{123}
  {1}{2}{3}{12}{23}     {1}{2}{3}{12}{13}{123}
  {1}{2}{3}{13}{23}     {1}{2}{3}{12}{23}{123}
  {1}{2}{12}{13}{23}    {1}{2}{3}{13}{23}{123}
  {1}{2}{3}{12}{123}    {1}{2}{12}{13}{23}{123}
  {1}{2}{3}{13}{123}    {1}{3}{12}{13}{23}{123}
  {1}{2}{3}{23}{123}    {2}{3}{12}{13}{23}{123}
  {1}{3}{12}{13}{23}
  {2}{3}{12}{13}{23}
  {1}{2}{13}{23}{123}
  {1}{3}{12}{23}{123}
  {2}{3}{12}{13}{123}
  {1}{12}{13}{23}{123}
  {2}{12}{13}{23}{123}
  {3}{12}{13}{23}{123}

Crossrefs

Covering set-systems are A003465.
Covering set-systems whose dual is strict are A059201.
The T_1 case is A326961.
The BII-numbers of these set-systems are A326966.
The non-covering case is A326968.
The unlabeled version is A326973.
Cf. A006126, A059052, A059523, A326950, A326960, A326965, A326969, A326971, A326974, A326975, A326978.

Programs

  • Mathematica
    dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&stableQ[dual[#],SubsetQ]&]],{n,0,3}]

Formula

Inverse binomial transform of A326968.

A245567 Number of antichain covers of a labeled n-set such that for every two distinct elements in the n-set, there is a set in the antichain cover containing one of the elements but not the other.

Original entry on oeis.org

2, 1, 1, 5, 76, 5993, 7689745, 2414465044600, 56130437141763247212112, 286386577668298408602599478477358234902247
Offset: 0

Views

Author

Patrick De Causmaecker, Jul 25 2014

Keywords

Comments

This is the number of antichain covers such that the induced partition contains only singletons. The induced partition of {{1,2},{2,3},{1,3},{3,4}} is {{1},{2},{3},{4}}, while the induced partition of {{1,2,3},{2,3,4}} is {{1},{2,3},{4}}.
This sequence is related to A006126. See 1st formula.
The sequence is also related to Dedekind numbers through Stirling numbers of the second kind. See 2nd formula.
Sets of subsets of the described type are said to be T_0. - Gus Wiseman, Aug 14 2019

Examples

			For n = 0, a(0) = 2 by the antisets {}, {{}}.
For n = 1, a(1) = 1 by the antiset {{1}}.
For n = 2, a(2) = 1 by the antiset {{1},{2}}.
For n = 3, a(3) = 5 by the antisets {{1},{2},{3}}, {{1,2},{1,3}}, {{1,2},{2,3}}, {{1,3},{2,3}}, {{1,2},{1,3},{2,3}}.

Links

Crossrefs

Cf. A000372 (Dedekind numbers), A006126 (Number of antichain covers of a labeled n-set).
Sequences counting and ranking T_0 structures:
A000112 (unlabeled topologies),
A001035 (topologies),
A059201 (covering set-systems),
A245567 (antichain covers),
A309615 (covering set-systems closed under intersection),
A316978 (factorizations),
A319559 (unlabeled set-systems by weight),
A319564 (integer partitions),
A319637 (unlabeled covering set-systems),
A326939 (covering sets of subsets),
A326940 (set-systems),
A326941 (sets of subsets),
A326943 (covering sets of subsets closed under intersection),
A326944 (covering sets of subsets with {} and closed under intersection),
A326945 (sets of subsets closed under intersection),
A326946 (unlabeled set-systems),
A326947 (BII-numbers of set-systems),
A326948 (connected set-systems),
A326949 (unlabeled sets of subsets),
A326950 (antichains),
A326959 (set-systems closed under intersection),
A327013 (unlabeled covering set-systems closed under intersection),
A327016 (BII-numbers of topologies).

Programs

  • Mathematica
    dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Subsets[Range[n]]],Union@@#==Range[n]&&stableQ[#,SubsetQ]&&UnsameQ@@dual[#]&]],{n,0,3}] (* Gus Wiseman, Aug 14 2019 *)

Formula

A000372(n) = Sum_{k=0..n} S(n+1,k+1)*a(k).
a(n) = A006126(n) - Sum_{k=1..n-1} S(n,k)*a(k).
Were n > 0 and S(n,k) is the number of ways to partition a set of n elements into k nonempty subsets.
Inverse binomial transform of A326950, if we assume a(0) = 1. - Gus Wiseman, Aug 14 2019

Extensions

Definition corrected by Patrick De Causmaecker, Oct 10 2014
a(9), based on A000372, from Patrick De Causmaecker, Jun 01 2023

A327057 Number of antichains covering a subset of {1..n} where every two covered vertices appear together in some edge (cointersecting).

Original entry on oeis.org

1, 2, 4, 9, 36, 1572, 3750221
Offset: 0

Views

Author

Gus Wiseman, Aug 18 2019

Keywords

Comments

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. An antichain is a set of sets, none of which is a subset of any other. This sequence counts antichains whose dual is pairwise intersecting.

Examples

			The a(0) = 1 through a(3) = 9 antichains:
  {}  {}     {}       {}
      {{1}}  {{1}}    {{1}}
             {{2}}    {{2}}
             {{1,2}}  {{3}}
                      {{1,2}}
                      {{1,3}}
                      {{2,3}}
                      {{1,2,3}}
                      {{1,2},{1,3},{2,3}}

Crossrefs

Antichains are A000372.
The BII-numbers of these set-systems are the intersection of A326704 and A326853.
The covering case is A327020.
Cointersecting set-systems are A327039.
Cf. A006126, A051185, A245567, A305844, A326950, A327038, A327052.

Programs

  • Mathematica
    dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],stableQ[dual[#],Intersection[#1,#2]=={}&]&]],{n,0,5}]

Formula

Binomial transform of A327020.

A327062 Number of antichains of distinct sets covering a subset of {1..n} whose dual is a weak antichain.

Original entry on oeis.org

1, 2, 5, 16, 81, 2595
Offset: 0

Views

Author

Gus Wiseman, Aug 18 2019

Keywords

Comments

A set-system is a finite set of finite nonempty sets. Its elements are sometimes called edges. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. A weak antichain is a multiset of sets, none of which is a proper subset of any other.

Examples

			The a(0) = 1 through a(3) = 16 antichains:
  {}  {}     {}         {}
      {{1}}  {{1}}      {{1}}
             {{2}}      {{2}}
             {{1,2}}    {{3}}
             {{1},{2}}  {{1,2}}
                        {{1,3}}
                        {{2,3}}
                        {{1},{2}}
                        {{1,2,3}}
                        {{1},{3}}
                        {{2},{3}}
                        {{1},{2,3}}
                        {{2},{1,3}}
                        {{3},{1,2}}
                        {{1},{2},{3}}
                        {{1,2},{1,3},{2,3}}

Crossrefs

Antichains are A000372.
The covering case is A319639.
The non-isomorphic multiset partition version is A319721.
The BII-numbers of these set-systems are the intersection of A326910 and A326853.
Set-systems whose dual is a weak antichain are A326968.
The unlabeled version is A327018.
Cf. A006126, A318099, A293606, A326704, A326950, A327020, A327057.

Programs

  • Mathematica
    dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],stableQ[dual[#],SubsetQ]&]],{n,0,3}]

A327356 Number of connected separable antichains of nonempty sets covering n vertices (vertex-connectivity 1).

Original entry on oeis.org

0, 0, 1, 3, 40, 1365
Offset: 0

Views

Author

Gus Wiseman, Sep 11 2019

Keywords

Comments

An antichain is a set of sets, none of which is a subset of any other. It is covering if there are no isolated vertices.
The vertex-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.

Examples

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

Crossrefs

Column k = 1 of A327351.
The graphical case is A327336.
The unlabeled version is A327436.
Cf. A014466, A048143, A307249, A326786, A326950, A327062, A327112, A327114, A327334.

Programs

  • Mathematica
    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]]]]]]]]];
stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
vertConnSys[vts_,eds_]:=Min@@Length/@Select[Subsets[vts],Function[del,Length[del]==Length[vts]-1||csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],vertConnSys[Range[n],#]==1&]],{n,0,4}]

A319643 Number of non-isomorphic weight-n strict multiset partitions whose dual is an antichain of (not necessarily distinct) multisets.

Original entry on oeis.org

1, 1, 3, 6, 15, 29, 82, 179, 504, 1302, 3822
Offset: 0

Views

Author

Gus Wiseman, Sep 25 2018

Keywords

Comments

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.
From Gus Wiseman, Aug 15 2019: (Start)
Also the number of non-isomorphic T_0 weak antichains of weight n. The T_0 condition means that the dual is strict (no repeated edges). A weak antichain is a multiset of multisets, none of which is a proper submultiset of any other. For example, non-isomorphic representatives of the a(0) = 1 through a(4) = 15 T_0 weak antichains are:
{} {{1}} {{1,1}} {{1,1,1}} {{1,1,1,1}}
{{1},{1}} {{1,2,2}} {{1,2,2,2}}
{{1},{2}} {{1},{2,2}} {{1,1},{1,1}}
{{1},{1},{1}} {{1,1},{2,2}}
{{1},{2},{2}} {{1},{2,2,2}}
{{1},{2},{3}} {{1,2},{2,2}}
{{1},{2,3,3}}
{{1,3},{2,3}}
{{1},{1},{2,2}}
{{1},{2},{3,3}}
{{1},{1},{1},{1}}
{{1},{1},{2},{2}}
{{1},{2},{2},{2}}
{{1},{2},{3},{3}}
{{1},{2},{3},{4}}
(End)

Examples

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

Crossrefs

Cf. A006126, A007716, A059201, A283877, A293606, A316980, A316983, A318099, A319558, A319616-A319646.
Cf. A245567, A293993, A319721, A326704, A326950, A326973, A326978.

A327807 Triangle read by rows where T(n,k) is the number of unlabeled antichains of sets with n vertices and vertex-connectivity >= k.

Original entry on oeis.org

1, 2, 0, 4, 1, 0, 9, 3, 2, 0, 29, 14, 10, 6, 0, 209, 157, 128, 91, 54, 0
Offset: 0

Views

Author

Gus Wiseman, Sep 26 2019

Keywords

Comments

An antichain is a set of sets, none of which is a subset of any other.
The vertex-connectivity of a set-system is the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.

Examples

			Triangle begins:
    1
    2   0
    4   1   0
    9   3   2   0
   29  14  10   6   0
  209 157 128  91  54   0

Crossrefs

Column k = 0 is A306505.
Column k = 1 is A261006 (clutters), if we assume A261006(0) = A261006(1) = 0.
Column k = 2 is A305028 (blobs), if we assume A305028(0) = A305028(2) = 0.
Except for the first column, same as A327358 (the covering case).
The labeled version is A327806.
Cf. A014466, A293606, A326704, A326950, A327062, A327334, A327350, A327351, A327805, A327808.
Showing 1-7 of 7 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.