A324167 Number of non-crossing antichain covers of {1,...,n}.

1, 1, 2, 9, 67, 633, 6763, 77766, 938957, 11739033, 150649945, 1973059212, 26265513030, 354344889798, 4833929879517, 66568517557803, 924166526830701, 12920482325488761, 181750521972603049, 2570566932237176232, 36532394627404815308, 521439507533582646156

Offset

0,3

Comments

An antichain is non-crossing if no pair of distinct parts is of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

Formula

Inverse binomial transform of A324168.

Binomial transform of A359984. - Andrew Howroyd, Jan 20 2023

Example

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

Mathematica

nn=6;
croXQ[stn_]:=MatchQ[stn, {___, {___, x_, ___, y_, ___}, ___, {___, z_, ___, t_, ___}, ___}/; x<z<y<t||z<x<t<y];
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[##]||croXQ[{#1, #2}]&], Union@@#==Range[n]&]], {n, 0, nn}]

Prog

(PARI) seq(n)={my(f=O(1)); for(n=2, n, f = 1 + (4*x + x^2)*f^2 - 3*x^2*(1 + x)*f^3); Vec(subst(x*(1 + x^2*f^2 - 3*x^3*f^3), x, x/(1-x))/x) } \\ Andrew Howroyd, Jan 20 2023

Crossrefs

Cf. A000108, A000124, A000372 (antichains), A001006, A006126 (antichain covers), A014466, A048143, A054726 (non-crossing graphs), A099947, A261005, A283877, A306438.

Cf. A324166, A324168, A324169, A324170, A324171, A324173, A359984 (no singletons).

Sequence in context: A091795 A319286 A158952 * A296793 A366336 A352410

Adjacent sequences: A324164 A324165 A324166 * A324168 A324169 A324170

Keyword

nonn

Author

Gus Wiseman, Feb 17 2019

Extensions

Terms a(9) and beyond from Andrew Howroyd, Jan 20 2023

Status

approved