A281874 -id:A281874 - cp's OEIS frontend

A287822 Number T(n,k) of Dyck paths of semilength n such that the maximal number of peaks per level equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 3, 1, 1, 0, 5, 7, 1, 1, 0, 13, 18, 9, 1, 1, 0, 31, 59, 29, 11, 1, 1, 0, 71, 193, 112, 38, 13, 1, 1, 0, 181, 616, 405, 163, 48, 15, 1, 1, 0, 447, 1955, 1514, 648, 220, 59, 17, 1, 1, 0, 1111, 6244, 5565, 2571, 925, 288, 71, 19, 1, 1

Offset: 0

Alois P. Heinz, Jun 01 2017

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

			. T(4,1) = 5:                                             /\
.                  /\        /\      /\        /\        /  \
.                 /  \    /\/  \    /  \      /  \/\    /    \
.              /\/    \  /      \  /    \/\  /      \  /      \ .
.
. T(4,2) = 7:       /\      /\        /\/\    /\        /\  /\
.              /\/\/  \  /\/  \/\  /\/    \  /  \/\/\  /  \/  \ .
.
.                          /\/\
.               /\/\      /    \
.              /    \/\  /      \  .
.
. T(4,3) = 1:   /\/\/\
.              /      \  .
.
. T(4,4) = 1:  /\/\/\/\  .
.
Triangle T(n,k) begins:
  1;
  0,   1;
  0,   1,    1;
  0,   3,    1,    1;
  0,   5,    7,    1,   1;
  0,  13,   18,    9,   1,   1;
  0,  31,   59,   29,  11,   1,  1;
  0,  71,  193,  112,  38,  13,  1,  1;
  0, 181,  616,  405, 163,  48, 15,  1, 1;
  0, 447, 1955, 1514, 648, 220, 59, 17, 1, 1;
  ...

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

Columns k=0-10 give: A000007, A281874 (for n>0), A288743, A288744, A288745, A288746, A288747, A288748, A288749, A288750, A288751.
Row sums give A000108.
T(2n,n) gives A287860.
Cf. A287847.

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

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

T(n,k) = A287847(n,k) - A287847(n,k-1) for k>0, T(n,0) = A000007(n).

A287847 Number A(n,k) of Dyck paths of semilength n such that no level has more than k peaks; square array A(n,k), n >= 0, k >= 0, read by descending antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 3, 0, 1, 1, 2, 4, 5, 0, 1, 1, 2, 5, 12, 13, 0, 1, 1, 2, 5, 13, 31, 31, 0, 1, 1, 2, 5, 14, 40, 90, 71, 0, 1, 1, 2, 5, 14, 41, 119, 264, 181, 0, 1, 1, 2, 5, 14, 42, 130, 376, 797, 447, 0, 1, 1, 2, 5, 14, 42, 131, 414, 1202, 2402, 1111, 0

Offset: 0

Alois P. Heinz, Jun 01 2017

			. A(3,1) = 3:                    /\
.                 /\    /\      /  \
.              /\/  \  /  \/\  /    \   .
.
. A(3,2) = 4:                            /\
.                 /\    /\      /\/\    /  \
.              /\/  \  /  \/\  /    \  /    \   .
.
. A(3,3) = 5:                                    /\
.                         /\    /\      /\/\    /  \
.              /\/\/\  /\/  \  /  \/\  /    \  /    \   .
.
Square array A(n,k) begins:
  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,   2,   2,   2,   2,   2,   2, ...
  0,  3,   4,   5,   5,   5,   5,   5, ...
  0,  5,  12,  13,  14,  14,  14,  14, ...
  0, 13,  31,  40,  41,  42,  42,  42, ...
  0, 31,  90, 119, 130, 131, 132, 132, ...
  0, 71, 264, 376, 414, 427, 428, 429, ...

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

Columns k=0-10 give: A000007, A281874, A287966, A287967, A287968, A287969, A287970, A287971, A287972, A287973, A287974.
Main diagonal and first two lower diagonals give: A000108, A001453, A120304.
Cf. A287822.

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

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

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

A(n,k) = Sum_{j=0..k} A287822(n,j).

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

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 1, 1, 0, 5, 2, 1, 1, 0, 13, 5, 3, 1, 1, 0, 31, 15, 4, 4, 1, 1, 0, 71, 27, 10, 7, 5, 1, 1, 0, 181, 76, 36, 11, 11, 6, 1, 1, 0, 447, 196, 83, 22, 19, 16, 7, 1, 1, 0, 1111, 548, 225, 81, 32, 31, 22, 8, 1, 1, 0, 2799, 1388, 573, 235, 60, 56, 48, 29, 9, 1, 1

Offset: 0

Alois P. Heinz, Jun 05 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,2) = 5:                                        /\/\
.                                       /\  /\      /    \
.      /\/\      /\/\      /\/\        /  \/  \    /      \
. /\/\/    \  /\/    \/\  /    \/\/\  /        \  /        \ .
.
. T(5,3) = 3:
.                                       /\/\/\
.              /\  /\/\    /\/\  /\    /      \
.             /  \/    \  /    \/  \  /        \ .
.
Triangle T(n,k) begins:
  1;
  0,   1;
  0,   1,  1;
  0,   3,  1,  1;
  0,   5,  2,  1,  1;
  0,  13,  5,  3,  1,  1;
  0,  31, 15,  4,  4,  1, 1;
  0,  71, 27, 10,  7,  5, 1, 1;
  0, 181, 76, 36, 11, 11, 6, 1, 1;

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

Columns k=0-10 give: A000007, A281874, A287843, A288110, A288111, A288112, A288113, A288114, A288115, A288116, A288117.
Row sums give A288109.
T(2n,n) gives A156043.
Cf. A000108, A288318.

b:= proc(n, k, j) option remember; `if`(n=j, 1, add(
      b(n-j, k, i)*(binomial(j-1, i-1)+binomial(i, k)
       *binomial(j-1, i-1-k)), i=1..min(j+k, n-j)))
    end:
T:= (n, k)-> 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[j - 1, i - 1] + Binomial[i, k]*Binomial[j - 1, i - 1 - k]), {i, 1, Min[j + k, n - j]}]];
T[n_, k_] := 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 *)

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

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

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

A287822 Number T(n,k) of Dyck paths of semilength n such that the maximal number of peaks per level equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A287847 Number A(n,k) of Dyck paths of semilength n such that no level has more than k peaks; square array A(n,k), n >= 0, k >= 0, read by descending antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

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

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

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