A152880 Number of Dyck paths of semilength n having exactly one peak of maximum height.

1, 1, 3, 8, 23, 71, 229, 759, 2566, 8817, 30717, 108278, 385509, 1384262, 5006925, 18225400, 66711769, 245400354, 906711758, 3363516354, 12522302087, 46773419089, 175232388955, 658295899526, 2479268126762, 9359152696924, 35406650450001, 134215036793130

Offset

1,3

Comments

Also number of peaks of maximum height in all Dyck paths of semilength n-1. Example: a(3)=3 because in (UD)(UD) and U(UD)D we have three peaks of maximum height (shown between parentheses).

Links

Alois P. Heinz, Table of n, a(n) for n = 1..500

Miklos Bona and Elijah DeJonge, Pattern avoiding permutations and involutions with a unique longest increasing subsequence, arXiv:2003.10640 [math.CO], 2020.

Miklós Bóna and Elijah DeJonge, Pattern Avoiding Permutations and Involutions with a Unique Longest Increasing Subsequence, (2020).

Formula

G.f.: g(z) = Sum_{j>=1} z^j/f(j)^2, where the f(j)'s are the Fibonacci polynomials (in z) defined by f(0)=f(1)=1, f(j)=f(j-1)-zf(j-2), j>=2.

a(n) = A152879(n,1).

a(n) = Sum_{k=1..n} k*A152879(n-1,k).

Example

a(3)=3 because we have UU(UD)DD, UDU(UD)D, U(UD)DUD, where U=(1,1), D=(1,-1), with the peak of maximum height shown between parentheses; the path UUDUDD does not qualify because it has two peaks of maximum height.

Maple

f[0] := 1: f[1] := 1: for i from 2 to 35 do f[i] := sort(expand(f[i-1]-z*f[i-2])) end do; g := sum(z^j/f[j]^2, j = 1 .. 34): gser := series(g, z = 0, 30): seq(coeff(gser, z, n), n = 1 .. 27);
# second Maple program:
b:= proc(x, y, h, c) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, c, add(b(x-1, y-i, max(h, y), `if`(h=y, 0,
     `if`(h<y, 1, c))), i=[1, -1])))
    end:
a:= n-> b(2*n, 0$3):
seq(a(n), n=1..28);  # Alois P. Heinz, Jul 25 2023

Mathematica

b[x_, y_, h_, c_] := b[x, y, h, c] = If[y<0 || y>x, 0, If[x==0, c, Sum[b[x-1, y-i, Max[h, y], If[h==y, 0, If[h<y, 1, c]]], {i, {1, -1}}]]];
a[n_] := b[2*n, 0, 0, 0];
Table[a[n], {n, 1, 28}] (* Jean-François Alcover, Sep 17 2024, after Alois P. Heinz *)

Crossrefs

Cf. A088457, A152879.

Column k=1 of A371928.

Sequence in context: A148776 A353067 A127385 * A259441 A176605 A080410

Adjacent sequences: A152877 A152878 A152879 * A152881 A152882 A152883

Keyword

nonn

Author

Emeric Deutsch, Jan 02 2009

Status

approved