A327355 -id:A327355 - cp's OEIS frontend

A120338 Number of disconnected antichain covers of a labeled n-set.

0, 1, 4, 30, 546, 41334, 54502904, 19317020441804

Offset: 1

Greg Huber, Jun 22 2006

nonn

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. - Gus Wiseman, Sep 26 2019

			a(3)=4: the four disconnected covers are {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}} and {{1},{2},{3}}.

Cf. A006126, A007153, A048143, A327355.
Column k = 0 of A327351, if we assume a(0) = 1.
Column k = 0 of A327357, if we assume a(0) = 1.
The non-covering version is A327354.
The unlabeled version is A327426.

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]]]];
Table[Length[Select[stableSets[Subsets[Range[n]],SubsetQ],Union@@#==Range[n]&&Length[csm[#]]!=1&]],{n,4}] (* Gus Wiseman, Sep 26 2019 *)

A327352 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of antichains of nonempty subsets of {1..n} with spanning edge-connectivity k.

Original entry on oeis.org

1, 1, 1, 4, 1, 14, 4, 1, 83, 59, 23, 2, 1232, 2551, 2792, 887, 107, 10, 1

Offset: 0

Gus Wiseman, Sep 10 2019

An antichain is a set of sets, none of which is a subset of any other.

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.

			Triangle begins:
     1
     1    1
     4    1
    14    4    1
    83   59   23    2
  1232 2551 2792  887  107   10    1
Row n = 3 counts the following antichains:
  {}             {{1,2,3}}      {{1,2},{1,3},{2,3}}
  {{1}}          {{1,2},{1,3}}
  {{2}}          {{1,2},{2,3}}
  {{3}}          {{1,3},{2,3}}
  {{1,2}}
  {{1,3}}
  {{2,3}}
  {{1},{2}}
  {{1},{3}}
  {{2},{3}}
  {{1},{2,3}}
  {{2},{1,3}}
  {{3},{1,2}}
  {{1},{2},{3}}

Row sums are A014466.
Column k = 0 is A327355.
The unlabeled version is A327438.
Cf. A052446, A327062, A327071, A327103, A327111, A327144, A327351, A327353.

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]]]];
spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],spanEdgeConn[Range[n],#]==k&]],{n,0,4},{k,0,2^n}]//.{foe___,0}:>{foe}

A327426 Number of non-connected, unlabeled, antichain covers of {1..n} (vertex-connectivity 0).

Original entry on oeis.org

1, 1, 1, 2, 6, 23, 201, 16345

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. A singleton is not considered connected.

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(2) = 1 through a(5) = 23 antichains:
    {1}{2}  {1}{23}    {1}{234}         {1}{2345}
            {1}{2}{3}  {12}{34}         {12}{345}
                       {1}{2}{34}       {1}{2}{345}
                       {1}{24}{34}      {1}{23}{45}
                       {1}{2}{3}{4}     {12}{35}{45}
                       {1}{23}{24}{34}  {1}{25}{345}
                                        {1}{2}{3}{45}
                                        {1}{245}{345}
                                        {1}{2}{35}{45}
                                        {1}{2}{3}{4}{5}
                                        {1}{24}{35}{45}
                                        {1}{25}{35}{45}
                                        {12}{34}{35}{45}
                                        {1}{24}{25}{345}
                                        {1}{23}{245}{345}
                                        {1}{2}{34}{35}{45}
                                        {1}{235}{245}{345}
                                        {1}{23}{24}{35}{45}
                                        {1}{25}{34}{35}{45}
                                        {1}{23}{24}{25}{345}
                                        {1}{234}{235}{245}{345}
                                        {1}{24}{25}{34}{35}{45}
                                        {1}{23}{24}{25}{34}{35}{45}

Column k = 0 of A327359.
The labeled version is A120338.
The non-covering version is A327424 (partial sums).
Cf. A014466, A261005, A327354, A327355, A327437.

a(n > 1) = A261005(n) - A261006(n).

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.

Original entry on oeis.org

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

Gus Wiseman, Sep 10 2019

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.

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

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.

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}

A327354 Number of disconnected or empty antichains of nonempty subsets of {1..n} (non-spanning edge-connectivity 0).

Original entry on oeis.org

1, 1, 2, 8, 53, 747, 45156, 54804920, 19317457655317

Offset: 0

Gus Wiseman, Sep 10 2019

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.

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

Column k = 0 of A327353.
The covering case is A120338.
The unlabeled version is A327426.
The spanning edge-connectivity version is A327352.
Cf. A014466, A326787, A327071, A327148, A327236, A327355, A327357.

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]]]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ],Length[csm[#]]!=1&]],{n,0,4}]

Equals the binomial transform of the exponential transform of A048143 minus A048143.

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

A327424 Number of unlabeled, non-connected or empty antichains of nonempty subsets of {1..n}.

Original entry on oeis.org

1, 1, 2, 4, 10, 33, 234, 16579

Offset: 0

Gus Wiseman, Sep 26 2019

An antichain is a set of nonempty sets, none of which is a subset of any other. A singleton is considered to be connected.

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

Partial sums of the positive-index terms of A327426.
The covering case is A327426.
The labeled version is A327354.
The labeled covering case is A120338.
Unlabeled antichains that are either not connected or not covering are A327437.
The case without empty antichains is A327808.
Cf. A014466, A293606, A326704, A327062, A327355.

A327808 Number of unlabeled, disconnected, nonempty antichains of subsets of {1..n}.

Original entry on oeis.org

0, 0, 1, 3, 9, 32, 233, 16578

Offset: 0

Gus Wiseman, Sep 26 2019

An antichain is a set of nonempty sets, none of which is a subset of any other. A singleton is considered to be connected.

			Non-isomorphic representatives of the a(2) = 1 through a(4) = 9 antichains:
   {{1},{2}}  {{1},{2}}      {{1},{2}}
              {{1},{2,3}}    {{1},{2,3}}
              {{1},{2},{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}}
                             {{4},{1,2},{1,3},{2,3}}

The labeled version is A327354 - 1.
The covering case is A327426.
Unlabeled antichains that are either not connected or not covering are A327437.
The version with empty antichains allowed is A327424.
Cf. A000372, A014466, A120338, A293606, A326704, A327062, A327355.

a(n) = A327424(n) - 1.

cp's OEIS Frontend

A120338 Number of disconnected antichain covers of a labeled n-set.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327352 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of antichains of nonempty subsets of {1..n} with spanning edge-connectivity k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327426 Number of non-connected, unlabeled, antichain covers of {1..n} (vertex-connectivity 0).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A327354 Number of disconnected or empty antichains of nonempty subsets of {1..n} (non-spanning edge-connectivity 0).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

A327424 Number of unlabeled, non-connected or empty antichains of nonempty subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

A327808 Number of unlabeled, disconnected, nonempty antichains of subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula