A289020 -id:A289020 - cp's OEIS frontend

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

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

Offset: 0

David Callan, Jan 31 2017

nonn

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.

			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.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Manosij Ghosh Dastidar and Michael Wallner, Bijections and congruences involving lattice paths and integer compositions, arXiv:2402.17849 [math.CO], 2024. See p. 19.

A048285 counts Dyck paths with nondecreasing peak heights.
Column k=1 of A287847, A288108.
Cf. A287846, A287901, A289020.

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}]

A287846 Number of Dyck paths of semilength n such that each positive level up to the highest nonempty level has exactly one peak.

Original entry on oeis.org

1, 1, 0, 2, 0, 4, 6, 8, 24, 52, 96, 212, 504, 1072, 2352, 5288, 11928, 26800, 60336, 136304, 308928, 701248, 1593120, 3622016, 8245008, 18787360, 42836928, 97724384, 223052784, 509338816, 1163512032, 2658731648, 6077117376, 13893874624, 31771515648

Offset: 0

Alois P. Heinz, Jun 01 2017

nonn

All terms with n > 1 are even.

			. a(1) = 1:    /\  .
.
. a(3) = 2:     /\       /\
.            /\/  \     /  \/\  .
.
. a(5) = 4:
.                /\       /\         /\       /\
.             /\/  \     /  \/\   /\/  \     /  \/\
.          /\/      \ /\/      \ /      \/\ /      \/\ .

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Manosij Ghosh Dastidar and Michael Wallner, Bijections and congruences involving lattice paths and integer compositions, arXiv:2402.17849 [math.CO], 2024. See p. 15.
Wikipedia, Counting lattice paths

Column k=1 of A288318.

Cf. A000108, A281874, A287843, A287845, A287901, A287963, A287987, A289020.

b:= proc(n, j) option remember; `if`(n=j or n=0, 1, add(
       b(n-j, i)*binomial(j-1, i-2)*i, i=1..min(j+2, n-j)))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..35);

b[n_, j_] := b[n, j] = If[n == j || n == 0, 1, Sum[b[n - j, i]*Binomial[j - 1, i - 2]*i, {i, 1, Min[j + 2, n - j]}]];
a[n_] := b[n, 1];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, May 23 2018, translated from Maple *)

A288972 Number A(n,k) of Dyck paths having exactly k peaks in each of the levels 1,...,n and no other peaks; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 9, 10, 1, 1, 1, 44, 471, 92, 1, 1, 1, 225, 27076, 82899, 1348, 1, 1, 1, 1182, 1713955, 102695344, 36913581, 28808, 1, 1, 1, 6321, 114751470, 147556480375, 1565018426896, 34878248649, 845800, 1

Offset: 0

Alois P. Heinz, Jun 20 2017

The semilengths of Dyck paths counted by A(n,k) are elements of the integer interval [k*n+n-1, k*n*(n+1)/2] for n,k>0.

			. A(3,1) = 10:
.
.        /\        /\          /\        /\
.     /\/  \      /  \/\    /\/  \      /  \/\
.  /\/      \  /\/      \  /      \/\  /      \/\
.
.                /\        /\                /\
.           /\  /  \      /  \  /\    /\    /  \
.        /\/  \/    \  /\/    \/  \  /  \/\/    \
.
.              /\        /\            /\
.         /\  /  \      /  \    /\    /  \  /\
.        /  \/    \/\  /    \/\/  \  /    \/  \/\  .
.
Square array A(n,k) begins:
  1,    1,        1,             1,                 1, ...
  1,    1,        1,             1,                 1, ...
  1,    2,        9,            44,               225, ...
  1,   10,      471,         27076,           1713955, ...
  1,   92,    82899,     102695344,      147556480375, ...
  1, 1348, 36913581, 1565018426896, 81072887990665625, ...

Alois P. Heinz, Antidiagonals n = 0..26, flattened
Wikipedia, Counting lattice paths

Columns k=0-2 give: A000012, A289020, A289054.
Rows n=0+1,2,3 give: A000012, A176479, A289030.
Main diagonal gives A288940.

b:= proc(n, k, j, v) option remember; `if`(n=j, `if`(v=1, 1, 0),
      `if`(v<2, 0, add(b(n-j, k, i, v-1)*(binomial(i, k)*
       binomial(j-1, i-1-k)), i=1..min(j+k, n-j))))
    end:
A:= proc(n, k) option remember; `if`(n=0 or k=0, 1,
      add(b(w, k, k, n), w=k*n+n-1..k*n*(n+1)/2))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[n_, k_, j_, v_]:=b[n, k, j, v]=If[n==j, If[v==1, 1, 0], If[v<2, 0, Sum[b[n - j, k, i, v - 1] Binomial[i, k] Binomial[j - 1, i - 1 - k], {i, Min[j + k, n - j]}]]]; A[n_, k_]:=A[n, k]=If[n==0 || k==0, 1, Sum[b[w, k, k, n], {w, k*n + n - 1, k*n*(n + 1)/2}]]; Table[A[n, d - n], {d, 0, 10}, {n, 0, d}] // Flatten (* Indranil Ghosh, Jul 06 2017, after Maple code *)

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A287846 Number of Dyck paths of semilength n such that each positive level up to the highest nonempty level has exactly one peak.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A288972 Number A(n,k) of Dyck paths having exactly k peaks in each of the levels 1,...,n and no other peaks; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica