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,14

Links

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

Wikipedia, Noncrossing partition

Example

=================================================================
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 ...
...

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 *)

Prog

(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))}

Crossrefs

Columns 2..5 are A006082(n+1), A082938, A303870, A303871.

Cf. A111275, A209612, A211359, A303694, A303875.

Sequence in context: A321724 A333737 A333733 * A303694 A194673 A240595

Adjacent sequences: A303926 A303927 A303928 * A303930 A303931 A303932

Keyword

nonn,tabl

Author

Andrew Howroyd, May 02 2018

Status

approved