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-4 of 4 results.

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

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 4, 3, 2, 0, 30, 40, 27, 17, 0, 546, 1365, 1842, 1690, 1451, 0, 41334
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
    1    1    0
    4    3    2    0
   30   40   27   17    0
  546 1365 1842 1690 1451    0

Crossrefs

Row sums are A307249, or A006126 if empty edges are allowed.
Column k = 0 is A120338, if we assume A120338(0) = A120338(1) = 1.
Column k = 1 is A327356.
Column k = n - 1 is A327020.
The unlabeled version is A327359.
The version for vertex-connectivity >= k is A327350.
The version for spanning edge-connectivity is A327352.
The version for non-spanning edge-connectivity is A327353, with covering case A327357.
Cf. A003465, A006126, A014466, A048143, A293993, A323818, A326704, A327125, A327334, A327336.

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 28 2021

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

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.

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-4 of 4 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.