login
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.
12

%I #29 Jun 04 2020 03:28:24

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

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

%U 1,16796,4856,864,245,57,1,1,1,1,1,1,58786,16282,2833,592,247,7,1,1,1,1,1,1

%N 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.

%C 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.

%H Alois P. Heinz, <a href="/A288386/b288386.txt">Rows n = 0..140, flattened</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>

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

%e T(4,1) = 6:

%e /\ /\ /\/\ /\ /\/\

%e /\/\/\/\ /\/\/ \ /\/ \/\ /\/ \ / \/\/\ / \/\ .

%e Triangle T(n,k) begins:

%e 1;

%e 1, 1;

%e 2, 1, 1;

%e 5, 3, 1, 1;

%e 14, 6, 1, 1, 1;

%e 42, 17, 4, 1, 1, 1;

%e 132, 49, 14, 1, 1, 1, 1;

%e 429, 147, 35, 5, 1, 1, 1, 1;

%e 1430, 459, 91, 30, 1, 1, 1, 1, 1;

%e 4862, 1476, 268, 96, 6, 1, 1, 1, 1, 1;

%p b:= proc(n, k, j) option remember; `if`(j=n, 1,

%p add(add(binomial(i, m)*binomial(j-1, i-1-m),

%p m=max(k, i-j)..i-1)*b(n-j, k, i), i=1..n-j))

%p end:

%p T:= proc(n, k) option remember; `if`(n=0, 1,

%p add(b(n, k, j), j=k..n))

%p end:

%p seq(seq(T(n, k), k=0..n), n=0..14);

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

%o (Python)

%o from sympy.core.cache import cacheit

%o from sympy import binomial

%o @cacheit

%o 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))

%o @cacheit

%o def T(n, k): return 1 if n==0 else sum(b(n, k, j) for j in range(k, n + 1))

%o for n in range(16): print([T(n, k) for k in range(n + 1)]) # _Indranil Ghosh_, Aug 09 2017

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

%Y Cf. A287847, A288387.

%K nonn,tabl

%O 0,4

%A _Alois P. Heinz_, Jun 08 2017