A048285 Number of Dyck paths of length 2n with nondecreasing peaks.

1, 1, 2, 4, 9, 21, 51, 126, 316, 800, 2040, 5230, 13464, 34773, 90035, 233590, 607011, 1579438, 4114014, 10725109, 27979704, 73035818, 190737623, 498320800, 1302341411, 3404552915, 8902154847, 23281653957, 60897957049, 159312797657

Offset: 0

Author

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

Keywords

• nonn
• nice

Comments

The name refers to weakly increasing peaks. The case of strictly increasing peaks is counted by A008930. - David Callan, Feb 18 2004

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

Row sums of A138155. - Emeric Deutsch, Mar 05 2008

For a constant 0.1199765127480778967304984... see A239528. - Vaclav Kotesovec, Mar 21 2014

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..690 (terms n=1..300 from Vaclav Kotesovec)
• Manosij Ghosh Dastidar and Michael Wallner, Bijections and congruences involving lattice paths and integer compositions, arXiv:2402.17849 [math.CO], 2024. See p. 21.
• Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.
• J. G. Penaud and O. Roques, Génération de chemins de Dyck à pics croissants, Discrete Mathematics, Vol. 246, no. 1-3 (2002), 255-267.

Crossrefs

Cf. A138155, A239528.

Programs

Maple

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
# second Maple program:
b:= proc(x, y, k, t) option remember; `if`(x=0, 1, `if`(y>0,
      `if`(t=1 and y>k, 0, b(x-1, y-1, `if`(t=1, min(k, y),
         k), 0)), 0) +`if`(y b(2*n, 0, n, 0):
seq(a(n), n=0..35);  # Alois P. Heinz, Jun 13 2017
# third Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, add(
      binomial(i, j)*add(b(n-2-(i-j)*2-2*t, i-j+t),
      t=0..n/2+j-i-1), j=0..i))
    end:
a:= n-> b(2*n, 0):
seq(a(n), n=0..35);  # Alois P. Heinz, Jun 13 2017

Mathematica

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

Formula

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

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

Extensions

More terms from Emeric Deutsch, Mar 05 2008

a(0)=1 prepended by Alois P. Heinz, Jan 31 2017