A287847 -id:A287847 - 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).

A288386 Number T(n,k) of Dyck paths of semilength n such that no positive level has fewer than k peaks; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 14, 6, 1, 1, 1, 42, 17, 4, 1, 1, 1, 132, 49, 14, 1, 1, 1, 1, 429, 147, 35, 5, 1, 1, 1, 1, 1430, 459, 91, 30, 1, 1, 1, 1, 1, 4862, 1476, 268, 96, 6, 1, 1, 1, 1, 1, 16796, 4856, 864, 245, 57, 1, 1, 1, 1, 1, 1, 58786, 16282, 2833, 592, 247, 7, 1, 1, 1, 1, 1, 1

Offset: 0

Alois P. Heinz, Jun 08 2017

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

			T(4,1) = 6:
                    /\      /\        /\/\    /\        /\/\
     /\/\/\/\  /\/\/  \  /\/  \/\  /\/    \  /  \/\/\  /    \/\ .
Triangle T(n,k) begins:
     1;
     1,    1;
     2,    1,   1;
     5,    3,   1,  1;
    14,    6,   1,  1, 1;
    42,   17,   4,  1, 1, 1;
   132,   49,  14,  1, 1, 1, 1;
   429,  147,  35,  5, 1, 1, 1, 1;
  1430,  459,  91, 30, 1, 1, 1, 1, 1;
  4862, 1476, 268, 96, 6, 1, 1, 1, 1, 1;

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

Columns k=0-10 give: A000108, A287901, A288678, A288679, A288680, A288681, A288682, A288683, A288684, A288685, A288686.

Cf. A287847, A288387.

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

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}]]; T[n_, k_]:=T[n, k]=If[n==0, 1, Sum[b[n, k, j], {j, k, n}]]; Table[T[n, k], {n, 0, 15}, {k, 0, n}] // Flatten (* 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))
@cacheit
def T(n, k): return 1 if n==0 else sum(b(n, k, j) for j in range(k, n + 1))
for n in range(16): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Aug 09 2017

T(n,k) = Sum_{i=k..n} A288387(n,i) if k <= n.

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

A287966 Number of Dyck paths of semilength n such that no level has more than two peaks.

Original entry on oeis.org

1, 1, 2, 4, 12, 31, 90, 264, 797, 2402, 7355, 22725, 70573, 220007, 688379, 2160568, 6798020, 21428295, 67644503, 213806475, 676499166, 2142338437, 6789119425, 21527297986, 68292751071, 216737768906, 688082702872, 2185085230180, 6940609839680, 22050162168754

Offset: 0

Alois P. Heinz, Jun 03 2017

nonn

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.
Wikipedia, Counting lattice paths

Column k=2 of A287847.

Cf. A000108.

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, Min[j + k, n - j]}]]; a[n_]:=If[n==0, 1, m=Min[n, 2]; Sum[b[n, m, j], {j, m}]]; Table[a[n], {n, 0, 50}] (* Indranil Ghosh, Aug 17 2017 *)

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))
def a(n):
    if n==0: return 1
    m=min(n, 2)
    return sum(b(n, m , j) for j in range(1, m + 1))
print([a(n) for n in range(51)]) # Indranil Ghosh, Aug 17 2017

a(n) = A287847(n,2).

a(n) = A000108(n) for n <= 2.

A287967 Number of Dyck paths of semilength n such that no level has more than three peaks.

Original entry on oeis.org

1, 1, 2, 5, 13, 40, 119, 376, 1202, 3916, 12920, 42974, 143989, 485623, 1646056, 5601850, 19127858, 65491001, 224750426, 772816118, 2661800949, 9180835248, 31703037147, 109586025511, 379124973003, 1312592051481, 4547284385059, 15761969520682, 54660238286990

Offset: 0

Alois P. Heinz, Jun 03 2017

nonn

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.
Wikipedia, Counting lattice paths

Column k=3 of A287847.

Cf. A000108.

a(n) = A287847(n,3).

a(n) = A000108(n) for n <= 3.

A287968 Number of Dyck paths of semilength n such that no level has more than four peaks.

Original entry on oeis.org

1, 1, 2, 5, 14, 41, 130, 414, 1365, 4564, 15491, 53147, 184014, 641710, 2251113, 7937416, 28108741, 99903584, 356181450, 1273253851, 4561936460, 16377201916, 58894487282, 212108951615, 764910126587, 2761577715513, 9980164366260, 36099265669505, 130675238973018

Offset: 0

Alois P. Heinz, Jun 03 2017

nonn

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

Column k=4 of A287847.

Cf. A000108.

a(n) = A287847(n,4).

a(n) = A000108(n) for n <= 4.

A287969 Number of Dyck paths of semilength n such that no level has more than five peaks.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 131, 427, 1413, 4784, 16416, 57042, 200151, 708109, 2522559, 9039042, 32550884, 117725760, 427372532, 1556523664, 5685148711, 20816785068, 76390832952, 280874946775, 1034505345468, 3816077176898, 14095932284899, 52131389039054

Offset: 0

Alois P. Heinz, Jun 03 2017

nonn

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

Column k=5 of A287847.

Cf. A000108.

a(n) = A287847(n,5).

a(n) = A000108(n) for n <= 5.

A287970 Number of Dyck paths of semilength n such that no level has more than six peaks.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 428, 1428, 4843, 16704, 58311, 205731, 732201, 2625406, 9473836, 34375133, 125325836, 458831723, 1686029403, 6215738207, 22981481106, 85189188184, 316514511424, 1178424867416, 4395603256233, 16423417124023, 61456310687426

Offset: 0

Alois P. Heinz, Jun 03 2017

nonn

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

Column k=6 of A287847.

Cf. A000108.

a(n) = A287847(n,6).

a(n) = A000108(n) for n <= 6.

A287971 Number of Dyck paths of semilength n such that no level has more than seven peaks.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1429, 4860, 16775, 58679, 207428, 739970, 2660157, 9627149, 35043221, 128207940, 471160868, 1738387703, 6436639288, 23908119163, 89056620547, 332583259981, 1244920744009, 4669782159158, 17550211110693, 66073189230521

Offset: 0

Alois P. Heinz, Jun 03 2017

nonn

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

Column k=7 of A287847.

Cf. A000108.

a(n) = A287847(n,7).

a(n) = A000108(n) for n <= 7.

A287972 Number of Dyck paths of semilength n such that no level has more than eight peaks.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4861, 16794, 58763, 207889, 742192, 2670734, 9676092, 35265848, 129205675, 475578542, 1757747362, 6520738724, 24270689885, 90609301618, 339193083093, 1272910714175, 4787750073615, 18045298493265, 68143016730029

Offset: 0

Alois P. Heinz, Jun 03 2017

nonn

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

Column k=8 of A287847.

Cf. A000108.

a(n) = A287847(n,8).

a(n) = A000108(n) for n <= 8.

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

A288386 Number T(n,k) of Dyck paths of semilength n such that no positive level has fewer than k peaks; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A287966 Number of Dyck paths of semilength n such that no level has more than two peaks.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

A287967 Number of Dyck paths of semilength n such that no level has more than three peaks.

Views

Author

Keywords

Links

Crossrefs

Formula

A287968 Number of Dyck paths of semilength n such that no level has more than four peaks.

Views

Author

Keywords

Links

Crossrefs

Formula

A287969 Number of Dyck paths of semilength n such that no level has more than five peaks.

Views

Author

Keywords

Links

Crossrefs

Formula

A287970 Number of Dyck paths of semilength n such that no level has more than six peaks.

Views

Author

Keywords

Links

Crossrefs

Formula

A287971 Number of Dyck paths of semilength n such that no level has more than seven peaks.

Views

Author

Keywords

Links

Crossrefs