A287846 -id:A287846 - cp's OEIS frontend

A288318 Number T(n,k) of Dyck paths of semilength n such that each positive level has exactly k peaks; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 0, 1, 0, 4, 3, 0, 0, 1, 0, 6, 6, 0, 0, 0, 1, 0, 8, 0, 4, 0, 0, 0, 1, 0, 24, 9, 20, 0, 0, 0, 0, 1, 0, 52, 54, 20, 5, 0, 0, 0, 0, 1, 0, 96, 138, 0, 45, 0, 0, 0, 0, 0, 1, 0, 212, 207, 16, 105, 6, 0, 0, 0, 0, 0, 1, 0, 504, 360, 200, 70, 84, 0, 0, 0, 0, 0, 0, 1

Offset: 0

Alois P. Heinz, Jun 07 2017

T(n,k) is defined for all n,k >= 0. The triangle contains only the terms for k<=n. T(0,k) = 1 and T(n,k) = 0 if k > n > 0.

			. T(5,1) = 4:
.               /\        /\          /\        /\
.            /\/  \      /  \/\    /\/  \      /  \/\
.         /\/      \  /\/      \  /      \/\  /      \/\ .
.
. T(5,2) = 3:
.              /\/\      /\/\      /\/\
.         /\/\/    \  /\/    \/\  /    \/\/\  .
.
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  0,  1;
  0,  2,  0,  1;
  0,  0,  0,  0, 1;
  0,  4,  3,  0, 0, 1;
  0,  6,  6,  0, 0, 0, 1;
  0,  8,  0,  4, 0, 0, 0, 1;
  0, 24,  9, 20, 0, 0, 0, 0, 1;
  0, 52, 54, 20, 5, 0, 0, 0, 0, 1;

Alois P. Heinz, Rows n = 0..140, flattened
Wikipedia, Counting lattice paths

Columns k=0-10 give: A000007, A287846, A287845, A288319, A288320, A288321, A288322, A288323, A288324, A288325, A288326.
Row sums give A287987.
Cf. A000108, A000984, A005564, A288108, A288940.

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

b[n_, k_, j_] := b[n, k, j] = If[n == j, 1, Sum[b[n - j, k, i]*(Binomial[i, k]*Binomial[j - 1, i - 1 - k]), {i, 1, Min[j + k, n - j]}]];
T[n_, k_] := If[n == 0, 1, b[n, k, k]];
Table[T[n, k], {n, 0, 14}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 25 2018, translated from Maple *)

T(n,n) = 1.
T(n+1,n) = 0.
T(2*n+1,n) = (n+1) for n>0.
T(2*n+2,n) = A005564(n+1) for n>1.
T(3*n,n) = A000984(n) = binomial(2*n,n).
T(3*n+1,n) = 0.
T(3*n+2,n) = (n+1)^2 for n>0.

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

Original entry on oeis.org

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

A287845 Number of Dyck paths of semilength n such that each positive level up to the highest nonempty level has exactly two peaks.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 6, 0, 9, 54, 138, 207, 360, 1368, 4545, 11304, 25182, 61605, 173916, 498798, 1347417, 3497328, 9147060, 24630669, 67414590, 184065966, 498495303, 1345622436, 3642036804, 9900361107, 26982011250, 73570082760, 200540053395, 546660151722

Offset: 0

Alois P. Heinz, Jun 01 2017

nonn

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

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=2 of A288318.

Cf. A000108, A281874, A287843, A287846, A287963, A287987.

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

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

A287987 Number of Dyck paths of semilength n such that all positive levels have the same number of peaks.

Original entry on oeis.org

1, 1, 1, 3, 1, 8, 13, 13, 54, 132, 280, 547, 1219, 3904, 11107, 25082, 53777, 137751, 419831, 1257599, 3453557, 8911341, 22636845, 59890162, 172264224, 529706648, 1630328686, 4765347773, 13125989799, 35253234315, 97531470556, 287880507391, 894915519516

Offset: 0

Alois P. Heinz, Jun 03 2017

nonn

			. a(3) = 3:                         /\        /\
.                    /\/\/\      /\/  \      /  \/\  .
.
. a(5) = 8:
.                       /\/\      /\/\      /\/\
.      /\/\/\/\/\  /\/\/    \  /\/    \/\  /    \/\/\
.
.            /\        /\          /\        /\
.         /\/  \      /  \/\    /\/  \      /  \/\
.      /\/      \  /\/      \  /      \/\  /      \/\  .

Alois P. Heinz, Table of n, a(n) for n = 0..500
Wikipedia, Counting lattice paths

Row sums of A288318.

Cf. A000108, A287845, A287846, A287993, A288109.

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

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

A287843 Number of Dyck paths of semilength n such that each level with peaks has exactly two peaks.

Original entry on oeis.org

1, 0, 1, 1, 2, 5, 15, 27, 76, 196, 548, 1388, 3621, 9894, 27553, 75346, 205634, 563729, 1565409, 4370226, 12191929, 33980329, 94874987, 265668404, 745652478, 2095025688, 5889310438, 16565399257, 46633521554, 131388795335, 370434641340, 1044917168292

Offset: 0

Alois P. Heinz, Jun 01 2017

nonn

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

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, Counting lattice paths

Cf. A000108, A281874, A287845, A287846, A287963.

Column k=2 of A288108.

b:= proc(n, j) option remember; `if`(n=j or n=0, 1,
      add(b(n-j, i)*(binomial(j-1, i-1) +i*(i-1)/2*
      binomial(j-1, i-3)), i=1..min(j+3, n-j)))
    end:
a:= n-> b(n, 2):
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-1] + i*(i-1)/2*Binomial[j-1, i-3]), {i, 1, Min[j + 3, n - j]}]];
a[n_] := b[n, 2];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, May 25 2018, translated from Maple *)

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

Original entry on oeis.org

1, 1, 1, 3, 6, 17, 49, 147, 459, 1476, 4856, 16282, 55466, 191474, 668510, 2356944, 8380944, 30025814, 108289093, 392871484, 1432934360, 5251507624, 19329771911, 71430479820, 264914270527, 985737417231, 3679051573264, 13769781928768, 51670641652576

Offset: 0

Alois P. Heinz, Jun 02 2017

nonn

			. a(3) = 3:
.                   /\      /\
.      /\/\/\    /\/  \    /  \/\ .
.
. a(4) = 6:
.                    /\      /\        /\/\    /\        /\/\
.     /\/\/\/\  /\/\/  \  /\/  \/\  /\/    \  /  \/\/\  /    \/\ .

Alois P. Heinz, Table of n, a(n) for n = 0..300
Wikipedia, Counting lattice paths

Column k=1 of A288386.

Cf. A000108, A281874, A287846.

b[n_, k_, j_]:=b[n, k, j]=If[j==n, 1, Sum[Sum[Binomial[i, m] Binomial[j - 1, i - 1 - m], {m, Max[k, i - j], i - 1}] b[n - j, k, i], {i, n - j}]];  a[n_]:=If[n==0, 1, Sum[b[n, 1, j], {j, n}]];Table[a[n], {n, 0, 30}] (* Indranil Ghosh, Aug 09 2017 *)

from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def b(n, k, j): return 1 if j==n else sum([sum([binomial(i, m)*binomial(j - 1, i - 1 - m) for m in range(max(k, i - j), i)])*b(n - j, k, i) for i in range(1, n - j + 1)])
def a(n): return 1 if n==0 else sum([b(n, 1, j) for j in range(1, n + 1)])
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 09 2017

A287963 Number of Dyck paths of semilength n such that each positive level up to the highest nonempty level has one or two peaks.

Original entry on oeis.org

1, 1, 1, 2, 5, 10, 28, 71, 194, 532, 1495, 4256, 12176, 35251, 102664, 300260, 881909, 2599948, 7688164, 22788527, 67676144, 201308938, 599676445, 1788564038, 5339905904, 15956230705, 47713265536, 142763240666, 427390085963, 1280058256294, 3835332884686

Offset: 0

Alois P. Heinz, Jun 03 2017

nonn

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

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, Counting lattice paths

Cf. A000108, A281874, A287843, A287845, A287846.

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

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

A289020 Number of Dyck paths having exactly one peak in each of the levels 1,...,n and no other peaks.

Original entry on oeis.org

1, 1, 2, 10, 92, 1348, 28808, 845800, 32664944, 1605553552, 97868465696, 7245440815264, 640359291096512, 66598657958731840, 8051483595083729024, 1119653568781387712128, 177465810459239319017216, 31804047327185301634148608, 6398867435594240638421950976

Offset: 0

Alois P. Heinz, Jun 22 2017

nonn

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

			. a(2) = 2:      /\    /\
.             /\/  \  /  \/\  .

Alois P. Heinz, Table of n, a(n) for n = 0..100
Wikipedia, Counting lattice paths

Column k=1 of A288972.

Cf. A000217, A060747, A281874, A287846.

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

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

cp's OEIS Frontend

A288318 Number T(n,k) of Dyck paths of semilength n such that each positive level has exactly k peaks; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A287845 Number of Dyck paths of semilength n such that each positive level up to the highest nonempty level has exactly two peaks.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A287987 Number of Dyck paths of semilength n such that all positive levels have the same number of peaks.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A287843 Number of Dyck paths of semilength n such that each level with peaks has exactly two peaks.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

A287963 Number of Dyck paths of semilength n such that each positive level up to the highest nonempty level has one or two peaks.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A289020 Number of Dyck paths having exactly one peak in each of the levels 1,...,n and no other peaks.

Views

Author

Keywords

Comments

Examples

Links