A295198 Number of noncrossing partitions up to rotation of an n-set without singleton blocks.

1, 0, 1, 1, 2, 2, 5, 6, 15, 28, 67, 145, 368, 870, 2211, 5549, 14290, 36824, 96347, 252927, 670142, 1783770, 4777951, 12855392, 34756783, 94345664, 257114389, 703150507, 1929404736, 5310364234, 14658134277, 40569137070, 112566363319, 313074271844, 872677323283

Offset: 0

Author

Andrew Howroyd, Nov 16 2017

Keywords

• nonn

Links

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

Crossrefs

Column k=0 of A211357.

Cf. A005043 (noncrossing partitions of an n-set without singleton blocks).

Cf. A002426.

Programs

Mathematica

b[0] = 1; b[1] = 0; b[n_] := b[n] = (n-1)*(2*b[n-1] + 3*b[n-2])/(n+1);
a[0] = 1; a[n_] := (b[n] + Sum[EulerPhi[n/d]*Coefficient[(1 + x + x^2)^d, x, d], {d, Most @ Divisors[n]}])/n;
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jul 03 2018, after Andrew Howroyd *)

PARI

\\ here b(n) is A005043.
b(n) = {polcoeff(serreverse((x - x^3) / (1 + x^3) + x * O(x*x^n)), n+1)}
a(n) = {if(n<1, n==0, (b(n) + sumdiv(n,d, if(d
				

Formula

a(n) = (1/n) * (A005043(n) - A002426(n) + Sum_{d|n} phi(n/d) * A002426(d)).