|
| |
|
|
A113337
|
|
Number of noncrossing partitions of [n] with all blocks of odd size and 1 and n in the same block.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
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
|
|
|
LINKS
|
|
|
|
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
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
|
|
|
EXAMPLE
|
a(4)=4 with the 4 partitions being 125/3/4, 135/2/4, 145/2/3 and 12345.
|
|
|
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 *)
|
|
|
PROG
|
(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
(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
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
