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

%I #9 Jan 20 2023 22:50:13

%S 1,1,2,9,67,633,6763,77766,938957,11739033,150649945,1973059212,

%T 26265513030,354344889798,4833929879517,66568517557803,

%U 924166526830701,12920482325488761,181750521972603049,2570566932237176232,36532394627404815308,521439507533582646156

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

%C 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.

%H Andrew Howroyd, <a href="/A324167/b324167.txt">Table of n, a(n) for n = 0..500</a>

%F Inverse binomial transform of A324168.

%F Binomial transform of A359984. - _Andrew Howroyd_, Jan 20 2023

%e The a(3) = 9 antichains:

%e {{1,2,3}}

%e {{1},{2,3}}

%e {{2},{1,3}}

%e {{3},{1,2}}

%e {{1,2},{1,3}}

%e {{1,2},{2,3}}

%e {{1,3},{2,3}}

%e {{1},{2},{3}}

%e {{1,2},{1,3},{2,3}}

%t nn=6;

%t croXQ[stn_]:=MatchQ[stn,{___,{___,x_,___,y_,___},___,{___,z_,___,t_,___},___}/;x<z<y<t||z<x<t<y];

%t 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]]]];

%t Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],SubsetQ[##]||croXQ[{#1,#2}]&],Union@@#==Range[n]&]],{n,0,nn}]

%o (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

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

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

%K nonn

%O 0,3

%A _Gus Wiseman_, Feb 17 2019

%E Terms a(9) and beyond from _Andrew Howroyd_, Jan 20 2023