A121483 Number of peaks at odd level in all nondecreasing Dyck paths of semilength n. A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing.
1, 2, 6, 19, 56, 167, 487, 1411, 4047, 11527, 32617, 91790, 257065, 716896, 1991792, 5515535, 15227846, 41930133, 115176023, 315676425, 863475561, 2357539227, 6425887551, 17487572124, 47522431681, 128969086382, 349567320762
Offset: 1
Keywords
Examples
a(2)=2 because in UDUD and UUDD we have altogether 2 peaks at odd level; here U=(1,1) and D=(1,-1).
Links
- E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
- Index entries for linear recurrences with constant coefficients, signature (6,-9,-5,15,-1,-4,1).
Programs
-
Maple
G:=z*(1-z)*(1-3*z+6*z^3-3*z^4)/(1+z)/(1-3*z+z^2)^2/(1-z-z^2): Gser:=series(G,z=0,33): seq(coeff(Gser,z,n),n=1..30);
-
Mathematica
Rest[CoefficientList[Series[x*(1-x)*(1-3*x+6*x^3-3*x^4)/(1+x)/(1-3*x+x^2)^2/(1-x-x^2), {x, 0, 20}], x]] (* Vaclav Kotesovec, Mar 20 2014 *)
Formula
G.f.: z(1-z)(1-3z+6z^3-3z^4)/[(1+z)(1-3z+z^2)^2*(1-z-z^2)].
Recurrence: (n^2 - 5*n - 20)*a(n) = (3*n^2 - 12*n - 79)*a(n-1) + (n^2 - 7*n - 16)*a(n-2) - (5*n^2 - 19*n - 138)*a(n-3) - (n^2 - 6*n - 31)*a(n-4) + (n^2 - 3*n - 24)*a(n-5). - Vaclav Kotesovec, Mar 20 2014
a(n) ~ (sqrt(5)-1) * (3+sqrt(5))^n * n / (5*2^(n+2)). - Vaclav Kotesovec, Mar 20 2014
Comments