A014466 -id:A014466 - cp's OEIS frontend

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.

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

Gus Wiseman, Sep 11 2019

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.

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

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.

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

Gus Wiseman, Sep 10 2019

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.

			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}

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.

A327437 Number of unlabeled antichains of nonempty subsets of {1..n} that are either non-connected or non-covering (spanning edge-connectivity 0).

Original entry on oeis.org

1, 1, 3, 6, 15, 52, 410, 32697

Offset: 0

Gus Wiseman, Sep 11 2019

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

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

Column k = 0 of A327438.
The labeled version is A327355.
The covering case is A327426.
Cf. A014466 A052446, A120338, A261005, A293606, A327201, A327236, A327352, A327353, A327354, A327438.

a(n > 0) = A306505(n) - A261006(n).

A344087 Flattened tetrangle of strict integer partitions sorted first by sum, then colexicographically.

Original entry on oeis.org

1, 2, 2, 1, 3, 3, 1, 4, 4, 1, 3, 2, 5, 3, 2, 1, 5, 1, 4, 2, 6, 4, 2, 1, 6, 1, 5, 2, 4, 3, 7, 5, 2, 1, 4, 3, 1, 7, 1, 6, 2, 5, 3, 8, 6, 2, 1, 5, 3, 1, 8, 1, 4, 3, 2, 7, 2, 6, 3, 5, 4, 9, 4, 3, 2, 1, 7, 2, 1, 6, 3, 1, 5, 4, 1, 9, 1, 5, 3, 2, 8, 2, 7, 3, 6, 4, 10

Offset: 0

Gus Wiseman, May 11 2021

The zeroth row contains only the empty partition.

A tetrangle is a sequence of finite triangles.

			Tetrangle begins:
  0: ()
  1: (1)
  2: (2)
  3: (21)(3)
  4: (31)(4)
  5: (41)(32)(5)
  6: (321)(51)(42)(6)
  7: (421)(61)(52)(43)(7)
  8: (521)(431)(71)(62)(53)(8)
  9: (621)(531)(81)(432)(72)(63)(54)(9)

Wikiversity, Lexicographic and colexicographic order

Positions of first appearances are A015724.
Triangle sums are A066189.
Taking revlex instead of colex gives A118457.
The not necessarily strict version is A211992.
Taking lex instead of colex gives A344086.
A026793 gives reversed strict partitions in A-S order (sum/length/lex).
A319247 sorts strict partitions by Heinz number.
A329631 sorts reversed strict partitions by Heinz number.
A344090 gives strict partitions in A-S order (sum/length/lex).
Cf. A005117, A014466, A209862.
Partition/composition orderings: A026791, A026792, A036036, A036037, A048793, A066099, A080576, A080577, A112798, A124734, A162247, A193073, A211992, A228100, A228351, A228531, A246688, A272020, A299755, A296774, A304038, A319247, A334301, A334302, A334439, A334442, A335122, A339351, A344085, A344086, A344088, A344089, A344091.
Partition/composition applications: A001793, A005183, A036043, A049085, A070939, A115623, A124736, A129129, A185974, A238966, A246867, A294648, A333483, A333484, A333485, A333486, A334433, A334434, A334435, A334436, A334437, A334438, A334440, A334441, A335123, A335124, A339195.

colex[f_,c_]:=OrderedQ[PadRight[{Reverse[f],Reverse[c]}]];
Table[Sort[Select[IntegerPartitions[n],UnsameQ@@#&],colex],{n,0,10}]

A344088 Flattened tetrangle of reversed strict integer partitions sorted first by sum, then colexicographically.

Original entry on oeis.org

1, 2, 1, 2, 3, 1, 3, 4, 2, 3, 1, 4, 5, 1, 2, 3, 2, 4, 1, 5, 6, 1, 2, 4, 3, 4, 2, 5, 1, 6, 7, 1, 3, 4, 1, 2, 5, 3, 5, 2, 6, 1, 7, 8, 2, 3, 4, 1, 3, 5, 4, 5, 1, 2, 6, 3, 6, 2, 7, 1, 8, 9, 1, 2, 3, 4, 2, 3, 5, 1, 4, 5, 1, 3, 6, 4, 6, 1, 2, 7, 3, 7, 2, 8, 1, 9, 10

Offset: 0

Gus Wiseman, May 12 2021

The zeroth row contains only the empty partition.

A tetrangle is a sequence of finite triangles.

			Tetrangle begins:
  0: ()
  1: (1)
  2: (2)
  3: (12)(3)
  4: (13)(4)
  5: (23)(14)(5)
  6: (123)(24)(15)(6)
  7: (124)(34)(25)(16)(7)
  8: (134)(125)(35)(26)(17)(8)
  9: (234)(135)(45)(126)(36)(27)(18)(9)

Wikiversity, Lexicographic and colexicographic order

Positions of first appearances are A015724.
Triangle sums are A066189.
The non-strict version is A080576.
Taking lex instead of colex gives A246688 (non-reversed: A344086).
The non-reversed version is A344087.
Taking revlex instead of colex gives A344089 (non-reversed: A118457).
A026793 gives reversed strict partitions in A-S order (sum/length/lex).
A319247 sorts strict partitions by Heinz number.
A329631 sorts reversed strict partitions by Heinz number.
A344090 gives strict partitions in A-S order (sum/length/lex).
Cf. A005117, A014466, A209862.
Partition/composition orderings: A026791, A026792, A036036, A036037, A048793, A066099, A080577, A112798, A124734, A162247, A193073, A211992, A228100, A228351, A228531, A272020, A299755, A296774, A304038, A334301, A334302, A334439, A334442, A335122, A339351, A344085, A344086, A344091.
Partition/composition applications: A001793, A005183, A036043, A049085, A070939, A115623, A124736, A129129, A185974, A238966, A246867, A294648, A333483, A333484, A333485, A333486, A334433, A334434, A334435, A334436, A334437, A334438, A334440, A334441, A335123, A335124, A339195.

colex[f_,c_]:=OrderedQ[PadRight[{Reverse[f],Reverse[c]}]];
Table[Sort[Reverse/@Select[IntegerPartitions[n],UnsameQ@@#&],colex],{n,0,10}]

A306550 Array read by antidiagonals where A(n,k) is the number of labeled k-antichains covering n vertices.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 6, 0, 0, 0, 0, 1, 25, 2, 0, 0, 0, 0, 1, 90, 56, 0, 0, 0, 0, 0, 1, 301, 790, 25, 0, 0, 0, 0, 0, 1, 966, 8380, 1895, 6, 0, 0, 0, 0, 0, 1, 3025, 76482, 70370, 2116, 1, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Feb 23 2019

			Array begins:
    n=0: n=1: n=2: n=3: n=4: n=5:
---------------------------------
k=0:  1    0    0    0    0    0
k=1:  1    1    1    1    1    1
k=2:  0    0    1    6   25   90
k=3:  0    0    0    2   56  790
k=4:  0    0    0    0   25 1895
k=5:  0    0    0    0    6 2116
Column n = 3 counts the following antichains:
  {{123}}  {{1}{23}}   {{1}{2}{3}}
           {{2}{13}}   {{12}{13}{23}}
           {{3}{12}}
           {{12}{13}}
           {{12}{23}}
           {{13}{23}}

Column sums are A006126. Row k = 2 is A000392. Rows k = 3-9 are A056046-A056049, A056052, A056101, A056104.

Cf. A000372, A006126, A006602, A014466, A261005, A305000, A305844, A317674.

nn=8;
stableSets[u_,Q_,k_]:=If[k==0,{{}},If[Length[u]==0,{},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q,k],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q,k-1]]]]];
ae[n_,k_]:=Length[Select[stableSets[Subsets[Range[n]],SubsetQ,k],Union@@#==Range[n]&]];
Table[ae[k,n-k],{n,0,nn},{k,0,n}]

A326364 Number of intersecting set systems with empty intersection (meaning there is no vertex in common to all the edges) covering n vertices.

Original entry on oeis.org

1, 0, 0, 2, 426, 987404, 887044205940, 291072121051815578010398, 14704019422368226413234332571239460300433492086, 12553242487939461785560846872353486129110194397301168776798213375239447299205732561174066488

Offset: 0

Gus Wiseman, Jul 01 2019

nonn

Covering means there are no isolated vertices. A set system (set of sets) is intersecting if no two edges are disjoint.

			The a(3) = 2 intersecting set systems with empty intersection:
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

Covering set systems with empty intersection are A318128.
Covering, intersecting set systems are A305843.
Covering, intersecting antichains with empty intersection are A326365.
Cf. A006126, A007363, A014466, A051185, A058891, A305844, A307249, A318129, A326361, A326362, A326363.

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],{1,n}],Intersection[#1,#2]=={}&],And[Union@@#==Range[n],#=={}||Intersection@@#=={}]&]],{n,0,4}]

Inverse binomial transform of A326373. - Andrew Howroyd, Aug 12 2019

a(6)-a(9) from Andrew Howroyd, Aug 12 2019

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

Gus Wiseman, Sep 11 2019

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.

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

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.

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

A326372 Number of intersecting antichains of (possibly empty) subsets of {1..n}.

Original entry on oeis.org

2, 3, 5, 13, 82, 2647, 1422565, 229809982113, 423295099074735261881

Offset: 0

Gus Wiseman, Jul 01 2019

A set system (set of sets) is an antichain if no edge is a subset of any other, and is intersecting if no two edges are disjoint.

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

The case without empty edges is A001206.
The inverse binomial transform is the spanning case A305844.
The unlabeled case is A306007.
Maximal intersecting antichains are A326363.
Intersecting set systems are A051185.
Cf. A000372, A007363, A014466, A305843, A326361, A326362.

a(n) = A001206(n + 1) + 1.

A326373 Number of intersecting set systems with empty intersection (meaning there is no vertex in common to all the edges) on n vertices.

Original entry on oeis.org

1, 1, 1, 3, 435, 989555, 887050136795, 291072121058024908202443, 14704019422368226413236661148207899662350666147, 12553242487939461785560846872353486129110194529637343578112251094358919036718815137721635299

Offset: 0

Gus Wiseman, Jul 01 2019

nonn

A set system (set of sets) is intersecting if no two edges are disjoint.

			The a(3) = 3 intersecting set systems with empty intersection:
  {}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

The inverse binomial transform is the covering case A326364.
Set systems with empty intersection are A318129.
Intersecting set systems are A051185.
Intersecting antichains with empty intersection are A326366.
Cf. A000371, A006126, A007363, A014466, A058891, A305844, A307249, A318128, A326361, A326362, A326363, A326365.

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],{1,n}],Intersection[#1,#2]=={}&],And[#=={}||Intersection@@#=={}]&]],{n,0,4}]

a(n) = A051185(n) - 1 - Sum_{k=1..n-1} binomial(n,k)*A000371(k). - Andrew Howroyd, Aug 12 2019

a(6)-a(9) from Andrew Howroyd, Aug 12 2019

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

A327437 Number of unlabeled antichains of nonempty subsets of {1..n} that are either non-connected or non-covering (spanning edge-connectivity 0).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A344087 Flattened tetrangle of strict integer partitions sorted first by sum, then colexicographically.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A344088 Flattened tetrangle of reversed strict integer partitions sorted first by sum, then colexicographically.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A306550 Array read by antidiagonals where A(n,k) is the number of labeled k-antichains covering n vertices.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A326364 Number of intersecting set systems with empty intersection (meaning there is no vertex in common to all the edges) covering n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326372 Number of intersecting antichains of (possibly empty) subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs