login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A281874 Number of Dyck paths of semilength n with distinct peak heights. 10
1, 1, 1, 3, 5, 13, 31, 71, 181, 447, 1111, 2799, 7083, 17939, 45563, 115997, 295827, 755275, 1929917, 4935701, 12631111, 32340473, 82837041, 212248769, 543978897, 1394481417, 3575356033, 9168277483, 23512924909, 60306860253, 154689354527, 396809130463 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

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.

It appears that lim a(n)/a(n-1) as n approaches infinity exists and is approximately 2.5659398.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

EXAMPLE

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.

MATHEMATICA

a[n_, k_] /; k == n := 1;

a[n_, k_] /; (k > n || k < 1) := 0;

a[n_, k_] :=

a[n, k] =

Sum[(Binomial[k - 1, i - 1] + i Binomial[k - 1, i - 2]) a[n - k,

i], {i, k + 1}];

Table[a[n, 1], {n, 28}]

CROSSREFS

A048285 counts Dyck paths with nondecreasing peak heights.

Column k=1 of A287847, A288108.

Cf. A287846, A287901, A289020.

Sequence in context: A062304 A354167 A350392 * A135532 A127600 A262237

Adjacent sequences: A281871 A281872 A281873 * A281875 A281876 A281877

KEYWORD

nonn

AUTHOR

David Callan, Jan 31 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 3 23:01 EST 2023. Contains 360045 sequences. (Running on oeis4.)