A359984 Number of non-crossing antichain covers of {1,...,n} without singletons.

1, 0, 1, 5, 40, 372, 3815, 41652, 474980, 5591912, 67454545, 829438722, 10358083621, 131013535954, 1674940506728, 21608978465341, 280976960703472, 3678460005228692, 48446069275681169, 641429612434785006, 8532711384899213885, 113988520118626013998

Offset

0,4

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.

All sets in the antichain include at least two vertices.

Links

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

Formula

Inverse binomial transform of A324167.

G.f.: 1 + x^2*F(x)^2 - 3*x^3*F(x)^3 where F(x) satisfies F(x) = 1 + (4*x + x^2)*F(x)^2 - 3*x^2*(1 + x)*F(x)^3 = 1 +4*x +30*x^2 +273*x^3 +2770*x^4 +30059*x^5+....

a(n) >= A324169(n).

Conjecture D-finite with recurrence 8*n*(n-1)*a(n) -4*(n-1)*(56*n-145)*a(n-1) +4*(101*n^2-682*n+996)*a(n-2) +2*(6200*n^2-47903*n+88131)*a(n-3) +2*(26985*n^2-234056*n+491978)*a(n-4) +2*(62749*n^2-628865*n+1584314)*a(n-5) +(n-5)*(121577*n-667756)*a(n-6) +38285*(n-5)*(n-6)*a(n-7)=0. - R. J. Mathar, Mar 10 2023

Example

The a(3) = 5 antichains:
  {{1,2,3}}
  {{1,2},{1,3}}
  {{1,2},{2,3}}
  {{1,3},{2,3}}
  {{1,2},{1,3},{2,3}}
The last 4 of these correspond to the graphs of A324169.

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(1 + x^2*f^2 - 3*x^3*f^3) } \\ Andrew Howroyd, Jan 20 2023

Crossrefs

Cf. A054726, A324167, A324168, A324169.

Sequence in context: A213104 A219560 A349362 * A271957 A220673 A376328

Adjacent sequences: A359981 A359982 A359983 * A359985 A359986 A359987

Keyword

nonn

Author

Andrew Howroyd, Jan 20 2023

Status

approved