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-10 of 11 results. Next

A120338 Number of disconnected antichain covers of a labeled n-set.

Original entry on oeis.org

0, 1, 4, 30, 546, 41334, 54502904, 19317020441804
Offset: 1

Views

Author

Greg Huber, Jun 22 2006

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. - Gus Wiseman, Sep 26 2019

Examples

			a(3)=4: the four disconnected covers are {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}} and {{1},{2},{3}}.

Crossrefs

Cf. A006126, A007153, A048143, A327355.
Column k = 0 of A327351, if we assume a(0) = 1.
Column k = 0 of A327357, if we assume a(0) = 1.
The non-covering version is A327354.
The unlabeled version is A327426.

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]]]];
Table[Length[Select[stableSets[Subsets[Range[n]],SubsetQ],Union@@#==Range[n]&&Length[csm[#]]!=1&]],{n,4}] (* Gus Wiseman, Sep 26 2019 *)

A327352 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of antichains of nonempty subsets of {1..n} with spanning edge-connectivity k.

Original entry on oeis.org

1, 1, 1, 4, 1, 14, 4, 1, 83, 59, 23, 2, 1232, 2551, 2792, 887, 107, 10, 1
Offset: 0

Views

Author

Gus Wiseman, Sep 10 2019

Keywords

Comments

An antichain is a set of sets, none of which is a subset of any other.
The spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (without removing incident vertices) to obtain a set-system that is disconnected or covers fewer vertices.

Examples

			Triangle begins:
     1
     1    1
     4    1
    14    4    1
    83   59   23    2
  1232 2551 2792  887  107   10    1
Row n = 3 counts the following antichains:
  {}             {{1,2,3}}      {{1,2},{1,3},{2,3}}
  {{1}}          {{1,2},{1,3}}
  {{2}}          {{1,2},{2,3}}
  {{3}}          {{1,3},{2,3}}
  {{1,2}}
  {{1,3}}
  {{2,3}}
  {{1},{2}}
  {{1},{3}}
  {{2},{3}}
  {{1},{2,3}}
  {{2},{1,3}}
  {{3},{1,2}}
  {{1},{2},{3}}

Crossrefs

Row sums are A014466.
Column k = 0 is A327355.
The unlabeled version is A327438.
Cf. A052446, A327062, A327071, A327103, A327111, A327144, A327351, A327353.

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]]]];
spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],spanEdgeConn[Range[n],#]==k&]],{n,0,4},{k,0,2^n}]//.{foe___,0}:>{foe}

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

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 9, 5, 2, 0, 114, 84, 44, 17, 0, 6894, 6348, 4983, 3141, 1451, 0, 7785062
Offset: 0

Views

Author

Gus Wiseman, Sep 09 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 empty or duplicate edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.
If empty edges are allowed, we have T(0,0) = 2.

Examples

			Triangle begins:
     1
     1    0
     2    1    0
     9    5    2    0
   114   84   44   17    0
  6894 6348 4983 3141 1451    0
The antichains counted in row n = 3:
  {123}         {123}         {123}
  {1}{23}       {12}{13}      {12}{13}{23}
  {2}{13}       {12}{23}
  {3}{12}       {13}{23}
  {12}{13}      {12}{13}{23}
  {12}{23}
  {13}{23}
  {1}{2}{3}
  {12}{13}{23}

Crossrefs

Column k = 0 is A307249, or A006126 if empty edges are allowed.
Column k = 1 is A048143 (clutters), if we assume A048143(0) = A048143(1) = 0.
Column k = 2 is A275307 (blobs), if we assume A275307(1) = A275307(2) = 0.
Column k = n - 1 is A327020 (cointersecting antichains).
The unlabeled version is A327358.
Negated first differences of rows are A327351.
BII-numbers of antichains are A326704.
Antichain covers are A006126.
Cf. A003465, A014466, A120338, A293606, A293993, A319639, A323818, A327112, A327125, A327334, A327336, A327352, A327356, A327357, A327358.

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],Union@@#==Range[n]&&vertConnSys[Range[n],#]>=k&]],{n,0,4},{k,0,n}]

Extensions

a(21) from Robert Price, May 24 2021

A327353 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of antichains of subsets of {1..n} with non-spanning edge-connectivity k.

Original entry on oeis.org

1, 1, 1, 2, 3, 8, 7, 3, 1, 53, 27, 45, 36, 6, 747, 511, 1497, 2085, 1540, 693, 316, 135, 45, 10, 1
Offset: 0

Views

Author

Gus Wiseman, Sep 10 2019

Keywords

Comments

An antichain is a set of sets, none of which is a subset of any other.
The non-spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (along with any non-covered vertices) to obtain a disconnected or empty set-system.

Examples

			Triangle begins:
    1
    1    1
    2    3
    8    7    3    1
   53   27   45   36    6
  747  511 1497 2085 1540  693  316  135   45   10    1
Row n = 3 counts the following antichains:
  {}             {{1}}      {{1,2},{1,3}}  {{1,2},{1,3},{2,3}}
  {{1},{2}}      {{2}}      {{1,2},{2,3}}
  {{1},{3}}      {{3}}      {{1,3},{2,3}}
  {{2},{3}}      {{1,2}}
  {{1},{2,3}}    {{1,3}}
  {{2},{1,3}}    {{2,3}}
  {{3},{1,2}}    {{1,2,3}}
  {{1},{2},{3}}

Crossrefs

Row sums are A014466.
Column k = 0 is A327354.
The covering case is A327357.
The version for spanning edge-connectivity is A327352.
The specialization to simple graphs is A327148, with covering case A327149, unlabeled version A327236, and unlabeled covering case A327201.
Cf. A052446, A307249, A326704, A326787, A327071, A327351, A327355.

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]]]];
eConn[sys_]:=If[Length[csm[sys]]!=1,0,Length[sys]-Max@@Length/@Select[Union[Subsets[sys]],Length[csm[#]]!=1&]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],eConn[#]==k&]],{n,0,4},{k,0,2^n}]//.{foe___,0}:>{foe}

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

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 5, 3, 2, 0, 20, 14, 10, 6, 0, 180, 157, 128, 91, 54, 0
Offset: 0

Views

Author

Gus Wiseman, Sep 09 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 empty or duplicate edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.
If empty edges are allowed, we have T(0,0) = 2.

Examples

			Triangle begins:
    1
    1   0
    2   1   0
    5   3   2   0
   20  14  10   6   0
  180 157 128  91  54   0
Non-isomorphic representatives of the antichains counted in row n = 4:
  {1234}          {1234}           {1234}           {1234}
  {1}{234}        {12}{134}        {123}{124}       {12}{134}{234}
  {12}{34}        {123}{124}       {12}{13}{234}    {123}{124}{134}
  {12}{134}       {12}{13}{14}     {12}{134}{234}   {12}{13}{14}{234}
  {123}{124}      {12}{13}{24}     {123}{124}{134}  {123}{124}{134}{234}
  {1}{2}{34}      {12}{13}{234}    {12}{13}{24}{34} {12}{13}{14}{23}{24}{34}
  {2}{13}{14}     {12}{134}{234}   {12}{13}{14}{234}
  {12}{13}{14}    {123}{124}{134}  {12}{13}{14}{23}{24}
  {12}{13}{24}    {12}{13}{14}{23} {123}{124}{134}{234}
  {1}{2}{3}{4}    {12}{13}{24}{34} {12}{13}{14}{23}{24}{34}
  {12}{13}{234}   {12}{13}{14}{234}
  {12}{134}{234}  {12}{13}{14}{23}{24}
  {123}{124}{134} {123}{124}{134}{234}
  {4}{12}{13}{23} {12}{13}{14}{23}{24}{34}
  {12}{13}{14}{23}
  {12}{13}{24}{34}
  {12}{13}{14}{234}
  {12}{13}{14}{23}{24}
  {123}{124}{134}{234}
  {12}{13}{14}{23}{24}{34}

Crossrefs

Column k = 0 is A261005, or A006602 if empty edges are allowed.
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.
Column k = n - 1 is A327425 (cointersecting).
The labeled version is A327350.
Negated first differences of rows are A327359.
Cf. A006126, A055621, A120338, A293606, A293993, A327334, A327351, A327356.

A327357 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of antichains of sets covering n vertices with non-spanning edge-connectivity k.

Original entry on oeis.org

1, 0, 1, 1, 1, 4, 1, 3, 1, 30, 13, 33, 32, 6, 546, 421, 1302, 1915, 1510, 693, 316, 135, 45, 10, 1
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 non-spanning edge-connectivity of a set-system is the minimum number of edges that must be removed (along with any non-covered vertices) to obtain a disconnected or empty set-system.

Examples

			Triangle begins:
    1
    0    1
    1    1
    4    1    3    1
   30   13   33   32    6
  546  421 1302 1915 1510  693  316  135   45   10    1
Row n = 3 counts the following antichains:
  {{1},{2,3}}    {{1,2,3}}  {{1,2},{1,3}}  {{1,2},{1,3},{2,3}}
  {{2},{1,3}}               {{1,2},{2,3}}
  {{3},{1,2}}               {{1,3},{2,3}}
  {{1},{2},{3}}

Crossrefs

Row sums are A307249.
Column k = 0 is A120338.
The non-covering version is A327353.
The version for spanning edge-connectivity is A327352.
The specialization to simple graphs is A327149, with unlabeled version A327201.
Cf. A014466, A293606, A326704, A326787, A327071, A327148, A327236, A327351.

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]]]];
eConn[sys_]:=If[Length[csm[sys]]!=1,0,Length[sys]-Max@@Length/@Select[Union[Subsets[sys]],Length[csm[#]]!=1&]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],Union@@#==Range[n]&&eConn[#]==k&]],{n,0,5},{k,0,2^n}]//.{foe___,0}:>{foe}

A327359 Triangle read by rows where T(n,k) is the number of unlabeled antichains of nonempty sets covering n vertices with vertex-connectivity exactly k.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 2, 1, 2, 0, 6, 4, 4, 6, 0, 23, 29, 37, 37, 54, 0
Offset: 0

Views

Author

Gus Wiseman, Sep 10 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 empty or duplicate edges) to obtain a non-connected set-system or singleton. Note that this means a single node has vertex-connectivity 0.
If empty edges are allowed, we have T(0,0) = 2.

Examples

			Triangle begins:
   1
   1  0
   1  1  0
   2  1  2  0
   6  4  4  6  0
  23 29 37 37 54  0
Row n = 4 counts the following antichains:
{1}{234}      {14}{234}        {134}{234}           {1234}
{12}{34}      {13}{24}{34}     {13}{14}{234}        {12}{134}{234}
{1}{2}{34}    {14}{24}{34}     {12}{13}{24}{34}     {124}{134}{234}
{1}{24}{34}   {14}{23}{24}{34} {13}{14}{23}{24}{34} {12}{13}{14}{234}
{1}{2}{3}{4}                                        {123}{124}{134}{234}
{1}{23}{24}{34}                                     {12}{13}{14}{23}{24}{34}

Crossrefs

Row sums are A261005, or A006602 if empty edges are allowed.
Column k = 0 is A327426.
Column k = 1 is A327436.
Column k = n - 1 is A327425.
The labeled version is A327351.
Cf. A003465, A006126, A014466, A048143, A293993, A323818, A326704, A327125, A327334, A327336, A327350, A327358.

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

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

Original entry on oeis.org

1, 2, 0, 5, 1, 0, 19, 5, 2, 0, 167, 84, 44, 17, 0
Offset: 0

Views

Author

Gus Wiseman, Sep 26 2019

Keywords

Comments

An antichain is a set of nonempty 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
    5   1   0
   19   5   2   0
  167  84  44  17   0

Crossrefs

Except for the first column, same as the covering case A327350.
Column k = 0 is A014466 (antichains).
Column k = 1 is A048143 (clutters), if we assume A048143(0) = A048143(1) = 0.
Column k = 2 is A275307 (blobs), if we assume A275307(1) = A275307(2) = 0.
The unlabeled version is A327807.
The case for vertex connectivity exactly k is A327351.
Cf. A014466, A293606, A326704, A327057, A327062, A327125, A327358.

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],#]>=k&]],{n,0,4},{k,0,n}]

A327436 Number of connected, unlabeled antichains of nonempty subsets of {1..n} covering n vertices with at least one cut-vertex (vertex-connectivity 1).

Original entry on oeis.org

0, 0, 1, 1, 4, 29
Offset: 0

Views

Author

Gus Wiseman, Sep 11 2019

Keywords

Examples

			Non-isomorphic representatives of the a(2) = 1 through a(5) = 29 antichains:
  {12}  {12}{13}  {12}{134}         {12}{1345}
                  {12}{13}{14}      {123}{145}
                  {12}{13}{24}      {12}{13}{145}
                  {12}{13}{14}{23}  {12}{13}{245}
                                    {13}{24}{125}
                                    {13}{124}{125}
                                    {14}{123}{235}
                                    {12}{13}{14}{15}
                                    {12}{13}{14}{25}
                                    {12}{13}{24}{35}
                                    {12}{13}{14}{235}
                                    {12}{13}{23}{145}
                                    {12}{13}{45}{234}
                                    {12}{14}{23}{135}
                                    {12}{15}{134}{234}
                                    {15}{23}{124}{134}
                                    {15}{123}{124}{134}
                                    {15}{123}{124}{234}
                                    {12}{13}{14}{15}{23}
                                    {12}{13}{14}{23}{25}
                                    {12}{13}{14}{23}{45}
                                    {12}{13}{15}{24}{34}
                                    {12}{13}{14}{15}{234}
                                    {12}{13}{14}{25}{234}
                                    {12}{13}{14}{15}{23}{24}
                                    {12}{13}{14}{15}{23}{45}
                                    {12}{13}{14}{23}{24}{35}
                                    {15}{123}{124}{134}{234}
                                    {12}{13}{14}{15}{23}{24}{34}

Crossrefs

Column k = 1 of A327359.
The labeled version is A327356.
Cf. A006602, A014466, A048143, A261005, A326704, A326786, A327112, A327114, A327426, A327334, A327336, A327350, A327351, A327358.

Formula

a(n > 2) = A261006(n) - A305028(n).
Showing 1-10 of 11 results. Next

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

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