A303929 Array read by antidiagonals: T(n,k) is the number of noncrossing partitions up to rotation and reflection composed of n blocks of size k.
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 3, 5, 6, 1, 1, 1, 1, 3, 8, 13, 12, 1, 1, 1, 1, 4, 11, 34, 49, 27, 1, 1, 1, 1, 4, 16, 60, 169, 201, 65, 1, 1, 1, 1, 5, 20, 109, 423, 1019, 940, 175, 1, 1, 1, 1, 5, 26, 167, 918, 3381, 6710, 4643, 490, 1
Offset: 0
Examples
================================================================= n\k| 1 2 3 4 5 6 7 8 9 ---+------------------------------------------------------------- 0 | 1 1 1 1 1 1 1 1 1 ... 1 | 1 1 1 1 1 1 1 1 1 ... 2 | 1 1 1 1 1 1 1 1 1 ... 3 | 1 2 2 3 3 4 4 5 5 ... 4 | 1 3 5 8 11 16 20 26 32 ... 5 | 1 6 13 34 60 109 167 257 359 ... 6 | 1 12 49 169 423 918 1741 3051 4969 ... 7 | 1 27 201 1019 3381 9088 20569 41769 77427 ... 8 | 1 65 940 6710 29335 96315 259431 607696 1280045 ... 9 | 1 175 4643 47104 266703 1072187 3417520 9240444 22066742 ... ...
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..1274
- Wikipedia, Noncrossing partition
Crossrefs
Programs
-
Mathematica
u[n_, k_, r_] := (r*Binomial[k*n + r, n]/(k*n + r)); e[n_, k_] := Sum[ u[j, k, 1 + (n - 2*j)*k/2], {j, 0, n/2}] c[n_, k_] := If[n == 0, 1, (DivisorSum[n, EulerPhi[n/#]*Binomial[k*#, #]&] + DivisorSum[GCD[n - 1, k], EulerPhi[#]*Binomial[n*k/#, (n - 1)/#]&])/(k*n) - Binomial[k*n, n]/(n*(k - 1) + 1)]; T[n_, k_] := (1/2)*(c[n, k] + If[n == 0, 1, If[OddQ[k], If[OddQ[n], 2*u[ Quotient[n, 2], k, (k + 1)/2], u[n/2, k, 1] + u[n/2 - 1, k, k]], e[n, k] + If[OddQ[n], u[Quotient[n, 2], k, k/2]]]/2]) /. Null -> 0; Table[T[n - k, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Jun 14 2018, translated from PARI *) -
PARI
\\ here c(n,k) is A303694 u(n,k,r) = {r*binomial(k*n + r, n)/(k*n + r)} e(n,k) = {sum(j=0, n\2, u(j, k, 1+(n-2*j)*k/2))} c(n, k)={if(n==0, 1, (sumdiv(n, d, eulerphi(n/d)*binomial(k*d, d)) + sumdiv(gcd(n-1, k), d, eulerphi(d)*binomial(n*k/d, (n-1)/d)))/(k*n) - binomial(k*n, n)/(n*(k-1)+1))} T(n,k)={(1/2)*(c(n,k) + if(n==0, 1, if(k%2, if(n%2, 2*u(n\2,k,(k+1)/2), u(n/2,k,1) + u(n/2-1,k,k)), e(n,k) + if(n%2, u(n\2,k,k/2)))/2))}