login
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.
2

%I #8 Jul 26 2022 11:55:41

%S 1,2,6,19,56,167,487,1411,4047,11527,32617,91790,257065,716896,

%T 1991792,5515535,15227846,41930133,115176023,315676425,863475561,

%U 2357539227,6425887551,17487572124,47522431681,128969086382,349567320762

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

%C a(n) = Sum(k*A121481(n,k),k=0..n).

%H E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, <a href="http://dx.doi.org/10.1016/S0012-365X(97)82778-1">Nondecreasing Dyck paths and q-Fibonacci numbers</a>, Discrete Math., 170, 1997, 211-217.

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (6,-9,-5,15,-1,-4,1).

%F G.f.: z(1-z)(1-3z+6z^3-3z^4)/[(1+z)(1-3z+z^2)^2*(1-z-z^2)].

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

%F a(n) ~ (sqrt(5)-1) * (3+sqrt(5))^n * n / (5*2^(n+2)). - _Vaclav Kotesovec_, Mar 20 2014

%e a(2)=2 because in UDUD and UUDD we have altogether 2 peaks at odd level; here U=(1,1) and D=(1,-1).

%p 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);

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

%Y Cf. A121481, A121486, A038731.

%K nonn

%O 1,2

%A _Emeric Deutsch_, Aug 02 2006