A327129 Number of connected set-systems covering n vertices with at least one edge whose removal (along with any non-covered vertices) disconnects the set-system (non-spanning edge-connectivity 1).

0, 1, 2, 35, 2804

Offset

0,3

Comments

A set-system is a finite set of finite nonempty sets. Elements of a set-system are sometimes called edges. 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..4.

Formula

Inverse binomial transform of A327196.

Example

The a(3) = 35 set-systems:
  {123}  {1}{12}{23}   {1}{2}{12}{13}   {1}{2}{3}{12}{13}
         {1}{13}{23}   {1}{2}{12}{23}   {1}{2}{3}{12}{23}
         {1}{2}{123}   {1}{2}{13}{23}   {1}{2}{3}{13}{23}
         {1}{3}{123}   {1}{2}{3}{123}   {1}{2}{3}{12}{123}
         {2}{12}{13}   {1}{3}{12}{13}   {1}{2}{3}{13}{123}
         {2}{13}{23}   {1}{3}{12}{23}   {1}{2}{3}{23}{123}
         {2}{3}{123}   {1}{3}{13}{23}
         {3}{12}{13}   {2}{3}{12}{13}
         {3}{12}{23}   {2}{3}{12}{23}
         {1}{23}{123}  {2}{3}{13}{23}
         {2}{13}{123}  {1}{2}{13}{123}
         {3}{12}{123}  {1}{2}{23}{123}
                       {1}{3}{12}{123}
                       {1}{3}{23}{123}
                       {2}{3}{12}{123}
                       {2}{3}{13}{123}

Mathematica

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
eConn[sys_]:=If[Length[csm[sys]]!=1, 0, Length[sys]-Max@@Length/@Select[Union[Subsets[sys]], Length[csm[#]]!=1&]];
Table[Length[Select[Subsets[Subsets[Range[n], {1, n}]], Union@@#==Range[n]&&eConn[#]==1&]], {n, 0, 3}]

Crossrefs

The restriction to simple graphs is A327079, with non-covering version A327231.

The version for spanning edge-connectivity is A327145, with BII-numbers A327111.

The BII-numbers of these set-systems are A327099.

The non-covering version is A327196.

Cf. A003465, A006129, A263296, A322395, A323818, A327071, A327149.

Sequence in context: A110697 A322514 A132100 * A291809 A182070 A325630

Adjacent sequences: A327126 A327127 A327128 * A327130 A327131 A327132

Keyword

nonn,more

Author

Gus Wiseman, Aug 27 2019

Status

approved