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,3

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

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.

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

Example

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

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<x-1, b(x-1, y+1, k, 1), 0))
    end:
a:= n-> 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 *)

Crossrefs

Cf. A138155, A239528.

Sequence in context: A261232 A176334 A257386 * A051529 A230554 A005207

Adjacent sequences: A048282 A048283 A048284 * A048286 A048287 A048288

Keyword

nonn,nice

Author

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

Extensions

More terms from Emeric Deutsch, Mar 05 2008

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

Status

approved