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

Author

Alois P. Heinz, Jun 01 2017

Keywords

• nonn
• tabl

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.

Examples

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

Links

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

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.

Programs

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

Formula

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