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

Author

Louis Shapiro, Jan 07 2006

Keywords

• nonn

Comments

If we only require blocks of odd size we get A101785. If G is the o.g.f. for A101785 then the o.g.f. for this sequence is (G-1)/(x*G). [corrected by David Callan, Nov 14 2021]

For n>=1, a(n) is the number of Dyck paths of semilength n-1 in which the last descent is of even length and all other descents are of odd length. For example, a(1) = 1 counts the empty path and a(5) = 4 counts UUUUDDDD, UUDUDUDD, UDUUDUDD, UDUDUUDD. - David Callan, Nov 14 2021

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