A113337 Number of noncrossing partitions of [n] with all blocks of odd size and 1 and n in the same block.
0, 1, 0, 1, 2, 4, 10, 26, 68, 183, 504, 1408, 3982, 11386, 32856, 95551, 279778, 824124, 2440440, 7260888, 21694352, 65066660, 195825872, 591217344, 1790081702, 5434311914, 16537576560, 50439949711, 154163497958, 472094359708, 1448302047274
Offset: 0
Keywords
Examples
a(4)=4 with the 4 partitions being 125/3/4, 135/2/4, 145/2/3 and 12345.
Links
- G. C. Greubel, Table of n, a(n) for n = 0..1000
- David Callan, Dyck path interpretation for sequences A101785, A113337 and A143017 in OEIS
- Helmut Prodinger, Partial Dyck path interpretation for three sequences in the Encyclopedia of Integer Sequences, arXiv:2408.01290 [math.CO], 2024.
Crossrefs
Cf. A101785.
Programs
-
Magma
[0,1,0] cat [(&+[2^(n-3*j)*Binomial(n-2,j-1)*Binomial(n-2*j-1, j-1)/j: j in [1..Floor(n/3)]]): n in [3..30]]; // G. C. Greubel, Apr 03 2019
-
Mathematica
Table[(-1)^n * Sum[((-1)^k*Binomial[n + k - 2, k - 1] * Binomial[2*n - 1, n - k] * Sum[Binomial[k, m] * (-1)^m * Sum[Binomial[n - j, -2*m + k + j - 1] * Binomial[n + 2*m - k - 2*j + 1, k - 1], {j, 2*m - k + 1, n}], {m, 0, n/2}])/k, {k, 1, n}], {n, 0, 30}] (* Vaclav Kotesovec, Sep 08 2016, after Vladimir Kruchinin *) Join[{0, 1}, Table[Sum[2^(n-3*j)*Binomial[n-2, j-1]*Binomial[n-2*j-1, j- 1]/j, {j,1,Floor[n/3]}], {n,2,30}]] (* G. C. Greubel, Apr 03 2019 *) -
Maxima
a(n):=(-1)^n*sum(((-1)^k*binomial(n+k-2,k-1)*binomial(2*n-1,n-k)*sum(binomial(k,m)*(-1)^m*sum(binomial(n-j,-2*m+k+j-1)*binomial(n+2*m-k-2*j+1,k-1),j,2*m-k+1,n),m,0,n/2))/k,k,1,n); /* Vladimir Kruchinin, Sep 08 2016 */
-
Maxima
a(n):=if n=1 then 1 else sum(2^(n-3*j)*binomial(n-2,j-1)*binomial(n-2*j-1,j-1)/j,j,1,floor((n)/3)); /* Vladimir Kruchinin, Apr 04 2019 */
-
PARI
a(n) = (-1)^n*sum(k=1, n, (-1)^k*binomial(n+k-2,k-1)*binomial(2*n-1,n-k)*sum(m=0,n/2, binomial(k,m)*(-1)^m*sum(j=2*m-k+1,n,(binomial(n-j,-2*m+k+j-1)*binomial(n+2*m-k-2*j+1,k-1))))/k); \\ Michel Marcus, Sep 08 2016
-
Sage
[0,1]+[sum(2^(n-3*j)*binomial(n-2,j-1)*binomial(n-2*j-1,j-1)/j for j in (1..floor(n/3))) for n in (2..30)] # G. C. Greubel, Apr 03 2019
Formula
a(n) = (-1)^n*Sum_{k=1..n} (((-1)^k*binomial(n+k-2,k-1)*binomial(2*n-1,n-k)*Sum_{m=0..n/2} (binomial(k,m)*(-1)^m*Sum_{j=2*m-k+1..n} (binomial(n-j,-2*m+k+j-1)*binomial(n+2*m-k-2*j+1,k-1))))/k). - Vladimir Kruchinin, Sep 08 2016
From Vaclav Kotesovec, Sep 08 2016: (Start)
Recurrence: 4*(n-1)*n*(91*n^2 - 543*n + 788)*a(n) = 6*(n-1)*(182*n^3 - 1359*n^2 + 3228*n - 2432)*a(n-1) - 4*(91*n^4 - 907*n^3 + 3119*n^2 - 4259*n + 1776)*a(n-2) + 12*(n-4)*(182*n^3 - 1359*n^2 + 3189*n - 2332)*a(n-3) - 5*(n-5)*(n-4)*(91*n^2 - 361*n + 336)*a(n-4).
a(n) ~ c * d^n / (sqrt(Pi) * n^(3/2)), where d = 3.2287049510945017293478492558... is the real root of the equation 5 - 24*d + 4*d^2 - 12*d^3 + 4*d^4 = 0 and c = 0.22436685378343740500658458471908821... is the positive real root of the equation -1 + 32*c^2 - 264*c^4 + 364*c^6 + 1820*c^8 = 0.
(End)
a(n) = Sum_{j=1..floor(n/3)} 2^(n-3*j)*C(n-2,j-1)*C(n-2*j-1,j-1)/j, a(1)=1. - Vladimir Kruchinin, Apr 04 2019
Comments