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