A324168 - OEIS

%I #12 Jan 20 2023 22:50:01

%S 1,2,5,19,120,1084,11783,141110,1791156,23646352,321220257,4459886776,

%T 63000867229,902528825332,13080523942476,191445447535373,

%U 2825542818304080,42005234042942228,628422035415996065,9454076958795999908,142933849346150225253,2170556938059142024688

%N Number of non-crossing antichains of nonempty subsets 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="/A324168/b324168.txt">Table of n, a(n) for n = 0..500</a>

%F Binomial transform of A324167.

%F G.f.: A(x) = B(x/(1-2*x))/x where B(x)/x is the g.f. of A359984. - _Andrew Howroyd_, Jan 20 2023

%e The a(0) = 1 through a(3) = 19 non-crossing antichains:

%e   {}  {}     {}        {}

%e       {{1}}  {{1}}     {{1}}

%e              {{2}}     {{2}}

%e              {{12}}    {{3}}

%e              {{1}{2}}  {{12}}

%e                        {{13}}

%e                        {{23}}

%e                        {{123}}

%e                        {{1}{2}}

%e                        {{1}{3}}

%e                        {{2}{3}}

%e                        {{1}{23}}

%e                        {{2}{13}}

%e                        {{3}{12}}

%e                        {{12}{13}}

%e                        {{12}{23}}

%e                        {{13}{23}}

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

%e                        {{12}{13}{23}}

%t nn=6;

%t nonXQ[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[stableSets[Subsets[Range[n],{1,n}],SubsetQ[##]||!nonXQ[{#1,#2}]&]],{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-2*x))/x) } \\ _Andrew Howroyd_, Jan 20 2023

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

%Y Cf. A324166, A324167, A324169, A324170, A324171, A324173, A359984.

%K nonn

%O 0,2

%A _Gus Wiseman_, Feb 17 2019

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