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

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.

Links

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

Wikipedia, Counting lattice paths

Formula

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

Example

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;

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

Prog

(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

Crossrefs

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

Cf. A287847, A288387.

Sequence in context: A106240 A340561 A097615 * A062993 A105556 A078920

Adjacent sequences: A288383 A288384 A288385 * A288387 A288388 A288389

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 08 2017

Status

approved