Voozh

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

(list; graph; refs; listen; history; text; internal format)

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

# Alternative:

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