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.

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,4

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.

Links

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

Example

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

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}

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.

Sequence in context: A262992 A036970 A110144 * A270230 A265366 A265365

Adjacent sequences: A327350 A327351 A327352 * A327354 A327355 A327356

Keyword

nonn,tabf,more

Author

Gus Wiseman, Sep 10 2019

Status

approved