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

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

Links

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

Formula

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

Example

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

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

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.

Sequence in context: A096053 A033470 A297594 * A339057 A016230 A327961

Adjacent sequences: A326566 A326567 A326568 * A326570 A326571 A326572

Keyword

nonn,more

Author

Gus Wiseman, Jul 18 2019

Extensions

a(8) from Andrew Howroyd, Aug 13 2019

Status

approved