login
Number of Dyck paths of length 2n with nondecreasing peaks.
9

%I #39 Mar 04 2024 15:02:31

%S 1,1,2,4,9,21,51,126,316,800,2040,5230,13464,34773,90035,233590,

%T 607011,1579438,4114014,10725109,27979704,73035818,190737623,

%U 498320800,1302341411,3404552915,8902154847,23281653957,60897957049,159312797657

%N Number of Dyck paths of length 2n with nondecreasing peaks.

%C The name refers to weakly increasing peaks. The case of strictly increasing peaks is counted by A008930. - _David Callan_, Feb 18 2004

%C a(n) ~ 0.11997*[(3+sqrt(5))/2]^n (Theorem 2 of the Penaud-Roques paper). - _Emeric Deutsch_, Mar 05 2008

%C Row sums of A138155. - _Emeric Deutsch_, Mar 05 2008

%C For a constant 0.1199765127480778967304984... see A239528. - _Vaclav Kotesovec_, Mar 21 2014

%H Alois P. Heinz, <a href="/A048285/b048285.txt">Table of n, a(n) for n = 0..690</a> (terms n=1..300 from Vaclav Kotesovec)

%H Manosij Ghosh Dastidar and Michael Wallner, <a href="https://arxiv.org/abs/2402.17849">Bijections and congruences involving lattice paths and integer compositions</a>, arXiv:2402.17849 [math.CO], 2024. See p. 21.

%H Sergi Elizalde, <a href="https://arxiv.org/abs/2008.05669">Symmetric peaks and symmetric valleys in Dyck paths</a>, arXiv:2008.05669 [math.CO], 2020.

%H J. G. Penaud and O. Roques, <a href="https://dx.doi.org/10.1016/S0012-365X(01)00261-8">Génération de chemins de Dyck à pics croissants</a>, Discrete Mathematics, Vol. 246, no. 1-3 (2002), 255-267.

%F G.f.: 1 + Sum_{n>=0} ((-1)^n x^{2n+1}(1-x)) / (Product_{i=1...n+1} ((1-x)(1-x^i)-x)).

%F Conjectural g.f.: Sum_{n>=0} (x*(1 - x))^n/( Product_{i=2..n+1} (1 - 2*x + x^i) ) (checked up to x^50). - _Peter Bala_, Mar 31 2017

%e a(3)=4 because we have UDUDUD, UDUUDD, UUDUDD and UUUDDD, where U=(1,1) and D=(1,-1).

%p g:= 1+sum((-1)^n*z^(2*n+1)*(1-z)/(product((1-z)*(1-z^i)-z,i=1..n+1)), n=0..40): gser:=series(g,z=0,35): seq(coeff(gser,z,n),n=0..30); # _Emeric Deutsch_, Mar 05 2008

%p # second Maple program:

%p b:= proc(x, y, k, t) option remember; `if`(x=0, 1, `if`(y>0,

%p `if`(t=1 and y>k, 0, b(x-1, y-1, `if`(t=1, min(k, y),

%p k), 0)), 0) +`if`(y<x-1, b(x-1, y+1, k, 1), 0))

%p end:

%p a:= n-> b(2*n, 0, n, 0):

%p seq(a(n), n=0..35); # _Alois P. Heinz_, Jun 13 2017

%p # third Maple program:

%p b:= proc(n, i) option remember; `if`(n=0, 1, add(

%p binomial(i, j)*add(b(n-2-(i-j)*2-2*t, i-j+t),

%p t=0..n/2+j-i-1), j=0..i))

%p end:

%p a:= n-> b(2*n, 0):

%p seq(a(n), n=0..35); # _Alois P. Heinz_, Jun 13 2017

%t Table[SeriesCoefficient[Sum[(-1)^k*x^(2*k+1)*(1-x)/Product[(1-x)*(1-x^i)-x,{i,1,k+1}],{k,0,n}],{x,0,n}],{n,1,20}] (* _Vaclav Kotesovec_, Mar 21 2014 *)

%Y Cf. A138155, A239528.

%K nonn,nice

%O 0,3

%A Olivier Roques (roques(AT)labri.u-bordeaux.fr)

%E More terms from _Emeric Deutsch_, Mar 05 2008

%E a(0)=1 prepended by _Alois P. Heinz_, Jan 31 2017