cp's OEIS Frontend

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

%I A152880 #39 Sep 19 2024 14:41:09
%S A152880 1,1,3,8,23,71,229,759,2566,8817,30717,108278,385509,1384262,5006925,
%T A152880 18225400,66711769,245400354,906711758,3363516354,12522302087,
%U A152880 46773419089,175232388955,658295899526,2479268126762,9359152696924,35406650450001,134215036793130
%N A152880 Number of Dyck paths of semilength n having exactly one peak of maximum height.
%C A152880 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).
%H A152880 Alois P. Heinz, <a href="/A152880/b152880.txt">Table of n, a(n) for n = 1..500</a>
%H A152880 Miklos Bona and Elijah DeJonge, <a href="https://arxiv.org/abs/2003.10640">Pattern avoiding permutations and involutions with a unique longest increasing subsequence</a>, arXiv:2003.10640 [math.CO], 2020.
%H A152880 Miklós Bóna and Elijah DeJonge, <a href="https://permutationpatterns.com/files/2020/06/WednesdayB_Bona.pdf">Pattern Avoiding Permutations and Involutions with a Unique Longest Increasing Subsequence</a>, (2020).
%F A152880 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.
%F A152880 a(n) = A152879(n,1).
%F A152880 a(n) = Sum_{k=1..n} k*A152879(n-1,k).
%e A152880 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.
%p A152880 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);
%p A152880 # second Maple program:
%p A152880 b:= proc(x, y, h, c) option remember; `if`(y<0 or y>x, 0,
%p A152880      `if`(x=0, c, add(b(x-1, y-i, max(h, y), `if`(h=y, 0,
%p A152880      `if`(h<y, 1, c))), i=[1, -1])))
%p A152880     end:
%p A152880 a:= n-> b(2*n, 0$3):
%p A152880 seq(a(n), n=1..28);  # _Alois P. Heinz_, Jul 25 2023
%t A152880 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}}]]];
%t A152880 a[n_] := b[2*n, 0, 0, 0];
%t A152880 Table[a[n], {n, 1, 28}] (* _Jean-François Alcover_, Sep 17 2024, after _Alois P. Heinz_ *)
%Y A152880 Cf. A088457, A152879.
%Y A152880 Column k=1 of A371928.
%K A152880 nonn
%O A152880 1,3
%A A152880 _Emeric Deutsch_, Jan 02 2009