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.

1, 1, 0, 1, 1, 0, 4, 3, 2, 0, 30, 40, 27, 17, 0, 546, 1365, 1842, 1690, 1451, 0, 41334

Offset

0,7

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.

Links

Table of n, a(n) for n=0..21.

Example

Triangle begins:
    1
    1    0
    1    1    0
    4    3    2    0
   30   40   27   17    0
  546 1365 1842 1690 1451    0

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

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.

Sequence in context: A200233 A373750 A350493 * A239475 A100802 A022960

Adjacent sequences: A327348 A327349 A327350 * A327352 A327353 A327354

Keyword

nonn,tabl,more

Author

Gus Wiseman, Sep 09 2019

Extensions

a(21) from Robert Price, May 28 2021

Status

approved