cp's OEIS Frontend

A287847 Number A(n,k) of Dyck paths of semilength n such that no level has more than k peaks; square array A(n,k), n >= 0, k >= 0, read by descending antidiagonals.

%I A287847 #31 Mar 21 2021 13:06:50
%S A287847 1,1,0,1,1,0,1,1,1,0,1,1,2,3,0,1,1,2,4,5,0,1,1,2,5,12,13,0,1,1,2,5,13,
%T A287847 31,31,0,1,1,2,5,14,40,90,71,0,1,1,2,5,14,41,119,264,181,0,1,1,2,5,14,
%U A287847 42,130,376,797,447,0,1,1,2,5,14,42,131,414,1202,2402,1111,0
%N A287847 Number A(n,k) of Dyck paths of semilength n such that no level has more than k peaks; square array A(n,k), n >= 0, k >= 0, read by descending antidiagonals.
%H A287847 Alois P. Heinz, <a href="/A287847/b287847.txt">Antidiagonals n = 0..140, flattened</a>
%H A287847 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>
%F A287847 A(n,k) = Sum_{j=0..k} A287822(n,j).
%e A287847 . A(3,1) = 3:                    /\
%e A287847 .                 /\    /\      /  \
%e A287847 .              /\/  \  /  \/\  /    \   .
%e A287847 .
%e A287847 . A(3,2) = 4:                            /\
%e A287847 .                 /\    /\      /\/\    /  \
%e A287847 .              /\/  \  /  \/\  /    \  /    \   .
%e A287847 .
%e A287847 . A(3,3) = 5:                                    /\
%e A287847 .                         /\    /\      /\/\    /  \
%e A287847 .              /\/\/\  /\/  \  /  \/\  /    \  /    \   .
%e A287847 .
%e A287847 Square array A(n,k) begins:
%e A287847   1,  1,   1,   1,   1,   1,   1,   1, ...
%e A287847   0,  1,   1,   1,   1,   1,   1,   1, ...
%e A287847   0,  1,   2,   2,   2,   2,   2,   2, ...
%e A287847   0,  3,   4,   5,   5,   5,   5,   5, ...
%e A287847   0,  5,  12,  13,  14,  14,  14,  14, ...
%e A287847   0, 13,  31,  40,  41,  42,  42,  42, ...
%e A287847   0, 31,  90, 119, 130, 131, 132, 132, ...
%e A287847   0, 71, 264, 376, 414, 427, 428, 429, ...
%p A287847 b:= proc(n, k, j) option remember; `if`(j=n, 1, add(
%p A287847       b(n-j, k, i)*add(binomial(i, m)*binomial(j-1, i-1-m),
%p A287847        m=max(0, i-j)..min(k, i-1)), i=1..min(j+k, n-j)))
%p A287847     end:
%p A287847 A:= proc(n, k) option remember; `if`(n=0, 1, (m->
%p A287847       add(b(n, m, j), j=1..m))(min(n, k)))
%p A287847     end:
%p A287847 seq(seq(A(n, d-n), n=0..d), d=0..14);
%t A287847 b[n_, k_, j_] := b[n, k, j] = If[j == n, 1, Sum[b[n - j, k, i]*Sum[ Binomial[i, m]*Binomial[j - 1, i - 1 - m], {m, Max[0, i - j], Min[k, i - 1]}], {i, 1, Min[j + k, n - j]}]];
%t A287847 A[n_, k_] := A[n, k] = If[n==0, 1, Sum[b[n, #, j], {j, 1, #}]&[Min[n, k]]];
%t A287847 Table[A[n, d - n], {d, 0, 14}, {n, 0, d}] // Flatten (* _Jean-François Alcover_, May 25 2018, translated from Maple *)
%o A287847 (Python)
%o A287847 from sympy.core.cache import cacheit
%o A287847 from sympy import binomial
%o A287847 @cacheit
%o A287847 def b(n, k, j): return 1 if j==n else sum([b(n - j, k, i)*sum([binomial(i, m)*binomial(j - 1, i - 1 - m) for m in range(max(0, i - j), min(k, i - 1) + 1)]) for i in range(1, min(j + k, n - j) + 1)])
%o A287847 @cacheit
%o A287847 def A(n, k):
%o A287847     if n==0: return 1
%o A287847     m=min(n, k)
%o A287847     return sum([b(n, m , j) for j in range(1, m + 1)])
%o A287847 for d in range(21): print([A(n, d - n) for n in range(d + 1)]) # _Indranil Ghosh_, Aug 16 2017
%Y A287847 Columns k=0-10 give: A000007, A281874, A287966, A287967, A287968, A287969, A287970, A287971, A287972, A287973, A287974.
%Y A287847 Main diagonal and first two lower diagonals give: A000108, A001453, A120304.
%Y A287847 Cf. A287822.
%K A287847 nonn,tabl
%O A287847 0,13
%A A287847 _Alois P. Heinz_, Jun 01 2017