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

Author

Emeric Deutsch, Jan 02 2009

Keywords

• nonn

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

Examples

			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.
		

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

Crossrefs

Cf. A088457, A152879.

Column k=1 of A371928.

Programs

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 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[hJean-François Alcover, Sep 17 2024, after Alois P. Heinz *)

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