A211355
Refined triangle A211359: T(n,k) is the number of noncrossing partitions up to rotation and reflection of an n-set that are of type k (k-th integer partition, defined by A194602).
Original entry on oeis.org
1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 3, 3, 5, 3, 3, 1, 2, 1, 1, 1, 1, 3, 4, 8, 4, 9, 3, 4, 4, 2, 1, 3, 1, 1, 1, 1, 4, 5, 14, 8, 19, 5, 14, 13, 8, 4, 12, 4, 4, 1, 3, 4, 3, 1, 1, 1, 1, 1, 4, 7, 20, 10, 38, 10, 30, 32, 16, 7, 48
Offset: 1
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.
Original entry on oeis.org
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
=================================================================
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 ...
...
-
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 *)
-
\\ 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))}
A211357
Triangle read by rows: T(n,k) is the number of noncrossing partitions up to rotation of an n-set that contain k singleton blocks.
Original entry on oeis.org
1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 2, 0, 1, 2, 3, 2, 2, 0, 1, 5, 6, 9, 4, 3, 0, 1, 6, 15, 18, 15, 5, 3, 0, 1, 15, 36, 56, 42, 29, 7, 4, 0, 1, 28, 91, 144, 142, 84, 42, 10, 4, 0, 1, 67, 232, 419, 432, 322, 152, 66, 12, 5, 0, 1, 145, 603, 1160, 1365, 1080, 630, 252, 90, 15, 5, 0, 1
Offset: 0
From _Andrew Howroyd_, Nov 16 2017: (Start)
Triangle begins: (n >= 0, 0 <= k <= n)
1;
0, 1;
1, 0, 1;
1, 1, 0, 1;
2, 1, 2, 0, 1;
2, 3, 2, 2, 0, 1;
5, 6, 9, 4, 3, 0, 1;
6, 15, 18, 15, 5, 3, 0, 1;
15, 36, 56, 42, 29, 7, 4, 0, 1;
28, 91, 144, 142, 84, 42, 10, 4, 0, 1;
67, 232, 419, 432, 322, 152, 66, 12, 5, 0, 1;
(End)
Cf.
A091867 (noncrossing partitions of an n-set with k singleton blocks),
A211359 (up to rotations and reflections).
-
a91867[n_, k_] := If[k == n, 1, (Binomial[n + 1, k]/(n + 1)) Sum[Binomial[n + 1 - k, j] Binomial[n - k - j - 1, j - 1], {j, 1, (n - k)/2}]];
a2426[n_] := Sum[Binomial[n, 2*k]*Binomial[2*k, k], {k, 0, Floor[n/2]}];
a171128[n_, k_] := Binomial[n, k]*a2426[n - k];
T[0, 0] = 1;
T[n_, k_] := (1/n)*(a91867[n, k] - a171128[n, k] + Sum[EulerPhi[d]* a171128[n/d, k/d], {d, Divisors[GCD[n, k]]}]);
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 03 2018, after Andrew Howroyd *)
-
g(x,y) = {1/sqrt((1 - (1 + y)*x)^2 - 4*x^2) - 1}
S(n)={my(A=(1-sqrt(1-4*x/(1-(y-1)*x) + O(x^(n+2))))/(2*x)-1); Vec(1+intformal((A + sum(k=2, n, eulerphi(k)*g(x^k + O(x*x^n), y^k)))/x))}
my(v=S(10)); for(n=1, #v, my(p=v[n]); for(k=0, n-1, print1(polcoeff(p,k), ", ")); print) \\ Andrew Howroyd, Nov 16 2017
A303931
Number of noncrossing partitions up to rotation and reflection of an n-set without singleton blocks.
Original entry on oeis.org
1, 0, 1, 1, 2, 2, 5, 6, 14, 22, 51, 95, 232, 498, 1239, 2953, 7520, 18920, 49235, 127917, 338094, 896060, 2397627, 6439730, 17403252, 47207620, 128628877, 351676075, 964909660, 2655474962, 7329668097, 20285420790, 56284927718, 156539620498, 436343744531
Offset: 0
-
\\ See A303875 for NCPartitionsModDihedral
Vec(NCPartitionsModDihedral(vector(40, k, k>1))) \\ Andrew Howroyd, May 02 2018
Showing 1-4 of 4 results.
Comments