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,8

Comments

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.

Links

Alois P. Heinz, Rows n = 0..100, flattened

Wikipedia, Counting lattice paths

Formula

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

Example

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

Maple

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

Mathematica

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

Crossrefs

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.

Sequence in context: A363756 A130160 A288108 * A162169 A216954 A124801

Adjacent sequences: A287819 A287820 A287821 * A287823 A287824 A287825

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 01 2017

Status

approved