cp's OEIS Frontend

A281874 Number of Dyck paths of semilength n with distinct peak heights.

%I A281874 #23 Mar 04 2024 15:03:41
%S A281874 1,1,1,3,5,13,31,71,181,447,1111,2799,7083,17939,45563,115997,295827,
%T A281874 755275,1929917,4935701,12631111,32340473,82837041,212248769,
%U A281874 543978897,1394481417,3575356033,9168277483,23512924909,60306860253,154689354527,396809130463
%N A281874 Number of Dyck paths of semilength n with distinct peak heights.
%C A281874 a(n) is the number of Dyck paths of length 2n with no two peaks at the same height. A peak is a UD, an up-step U=(1,1) immediately followed by a down-step D=(1,-1).
%C A281874 In the Mathematica recurrence below, a(n,k) is the number of Dyck paths of length 2n with all peaks at distinct heights except that there are k peaks at the maximum peak height. Thus a(n)=a(n,1). The recurrence is based on the following simple observation. Paths counted by a(n,k) are obtained from paths counted by a(n-k,i) for some i, 1<=i<=k+1, by inserting runs of one or more contiguous peaks at each of the existing peak vertices at the maximum peak height, except that (at most) one such existing peak may be left undisturbed, and so that a total of k new peaks are added.
%C A281874 It appears that lim a(n)/a(n-1) as n approaches infinity exists and is approximately 2.5659398.
%H A281874 Alois P. Heinz, <a href="/A281874/b281874.txt">Table of n, a(n) for n = 0..1000</a>
%H A281874 Manosij Ghosh Dastidar and Michael Wallner, <a href="https://arxiv.org/abs/2402.17849">Bijections and congruences involving lattice paths and integer compositions</a>, arXiv:2402.17849 [math.CO], 2024. See p. 19.
%e A281874 a(3)=3 counts UUUDDD, UDUUDD, UUDDUD because the first has only one peak and the last two have peak heights 1,2 and 2,1 respectively.
%t A281874 a[n_, k_] /; k == n := 1;
%t A281874 a[n_, k_] /; (k > n || k < 1) := 0;
%t A281874 a[n_, k_] :=
%t A281874 a[n, k] =
%t A281874   Sum[(Binomial[k - 1, i - 1] + i Binomial[k - 1, i - 2]) a[n - k,
%t A281874      i], {i, k + 1}];
%t A281874 Table[a[n, 1], {n, 28}]
%Y A281874 A048285 counts Dyck paths with nondecreasing peak heights.
%Y A281874 Column k=1 of A287847, A288108.
%Y A281874 Cf. A287846, A287901, A289020.
%K A281874 nonn
%O A281874 0,4
%A A281874 _David Callan_, Jan 31 2017