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

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.

Links

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

Wikipedia, Counting lattice paths

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.

Example

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

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

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.

Sequence in context: A029583 A382562 A011289 * A225678 A141720 A353449

Adjacent sequences: A288384 A288385 A288386 * A288388 A288389 A288390

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 08 2017

Status

approved