A288387 Number T(n,k) of Dyck paths of semilength n such that the minimal number of peaks over all positive levels equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 8, 5, 0, 0, 1, 25, 13, 3, 0, 0, 1, 83, 35, 13, 0, 0, 0, 1, 282, 112, 30, 4, 0, 0, 0, 1, 971, 368, 61, 29, 0, 0, 0, 0, 1, 3386, 1208, 172, 90, 5, 0, 0, 0, 0, 1, 11940, 3992, 619, 188, 56, 0, 0, 0, 0, 0, 1, 42504, 13449, 2241, 345, 240, 6, 0, 0, 0, 0, 0, 1

Offset: 0

Author

Alois P. Heinz, Jun 08 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.

T(0,0) = 1 by convention.

Examples

			. T(4,1) = 5:
.              /\      /\        /\/\    /\        /\/\
.         /\/\/  \  /\/  \/\  /\/    \  /  \/\/\  /    \/\ .
.
Triangle T(n,k) begins:
:    1;
:    0,    1;
:    1,    0,   1;
:    2,    2,   0,  1;
:    8,    5,   0,  0, 1;
:   25,   13,   3,  0, 0, 1;
:   83,   35,  13,  0, 0, 0, 1;
:  282,  112,  30,  4, 0, 0, 0, 1;
:  971,  368,  61, 29, 0, 0, 0, 0, 1;
: 3386, 1208, 172, 90, 5, 0, 0, 0, 0, 1;
		

Links

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

Crossrefs

Columns k=0-10 give: A288539, A288540, A288541, A288542, A288543, A288544, A288545, A288546, A288547, A288548, A288549.

Row sums give A000108.

Main diagonal and first lower diagonal give: A000012, A000004.

Cf. A000007, A000027, A218152, A287822, A288386.

Programs

Maple

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:
A:= proc(n, k) option remember; `if`(n=0, 1,
      add(b(n, k, j), j=k..n))
    end:
T:= (n, k)-> `if`(n=k, 1, A(n, k)-A(n, k+1)):
seq(seq(T(n, k), k=0..n), n=0..14);

Mathematica

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, 1, n - j}]];
A[n_, k_] := A[n, k] = If[n == 0, 1, Sum[b[n, k, j], {j, k, n}]];
T[n_, k_] := If[n == k, 1, A[n, k] - A[n, k + 1]];
Table[T[n, k], {n, 0, 14}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 25 2018, translated from Maple *)

Formula

T(0,0) = 1, T(n,k) = A288386(n,k) - A288386(n,k+1).

T(2n,n-1) = A218152(n) for n>1.

T(2n,n) = A000007(n).

T(2n+1,n) = A000027(n+1) for n>0.