A113337 - OEIS

%I #40 Aug 05 2024 08:42:02

%S 0,1,0,1,2,4,10,26,68,183,504,1408,3982,11386,32856,95551,279778,

%T 824124,2440440,7260888,21694352,65066660,195825872,591217344,

%U 1790081702,5434311914,16537576560,50439949711,154163497958,472094359708,1448302047274

%N Number of noncrossing partitions of [n] with all blocks of odd size and 1 and n in the same block.

%C 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]

%C 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

%H G. C. Greubel, <a href="/A113337/b113337.txt">Table of n, a(n) for n = 0..1000</a>

%H David Callan, <a href="/A113337/a113337.pdf">Dyck path interpretation for sequences A101785, A113337 and A143017 in OEIS</a>

%H Helmut Prodinger, <a href="https://arxiv.org/abs/2408.01290">Partial Dyck path interpretation for three sequences in the Encyclopedia of Integer Sequences</a>, arXiv:2408.01290 [math.CO], 2024.

%F 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

%F From _Vaclav Kotesovec_, Sep 08 2016: (Start)

%F 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).

%F 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.

%F (End)

%F 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

%e a(4)=4 with the 4 partitions being 125/3/4, 135/2/4, 145/2/3 and 12345.

%t 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_ *)

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

%o (Maxima)

%o 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 */

%o (Maxima)

%o 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 */

%o (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

%o (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

%o (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

%Y Cf. A101785.

%K nonn

%O 0,5

%A _Louis Shapiro_, Jan 07 2006