A326569 Number of covering antichains of subsets of {1..n} with no singletons and different edge-sizes.

1, 0, 1, 1, 13, 121, 2566, 121199, 13254529

Offset: 0

Author

Gus Wiseman, Jul 18 2019

Keywords

• nonn
• more

Comments

An antichain is a finite set of finite sets, none of which is a subset of any other. It is covering if its union is {1..n}. The edge-sizes are the numbers of vertices in each edge, so for example the edge sizes of {{1,3},{2,5},{3,4,5}} are {2,2,3}.

Examples

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

Crossrefs

Antichain covers are A006126.

Set partitions with different block sizes are A007837.

The case with singletons is A326570.

Cf. A000372, A003182, A306021, A307249, A326565, A326571, A326572, A326573.

Programs

Mathematica

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]]]];
cleq[n_]:=Select[stableSets[Subsets[Range[n],{2,n}],SubsetQ[#1,#2]||Length[#1]==Length[#2]&],Union@@#==Range[n]&];
Table[Length[cleq[n]],{n,0,6}]

Formula

a(n) = A326570(n) - n*a(n-1) for n > 0. - Andrew Howroyd, Aug 13 2019

Extensions

a(8) from Andrew Howroyd, Aug 13 2019