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.

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

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(0,k) = 1, T(n,k) = 0 for k > n > 0.

Examples

			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;
		

Links

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

Crossrefs

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

Cf. A287847, A288387.

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

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

Python

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

Formula

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