login
A375659
For 0<=k<=n, T(n,k) = the number of Dyck-type lattice paths of length n, starting at the point (0,k), triangle T read by rows.
1
1, 1, 2, 2, 3, 4, 3, 6, 7, 8, 6, 10, 14, 15, 16, 10, 20, 25, 30, 31, 32, 20, 35, 50, 56, 62, 63, 64, 35, 70, 91, 112, 119, 126, 127, 128, 70, 126, 182, 210, 238, 246, 254, 255, 256, 126, 252, 336, 420, 456, 492, 501, 510, 511, 512, 252, 462, 672, 792, 912, 957, 1002, 1012, 1022, 1023, 1024
OFFSET
0,3
COMMENTS
A Dyck type lattice path has the steps (1,1) or (1,-1) and never passes below the x-axis.
For k>=n, the number of Dyck-type lattice paths is 2^n.
The sequence completes A322291 by adding a diagonal of powers of 2.
LINKS
John Tyler Rascoe, Rows n = 0..140, flattened
FORMULA
T(n,k) = Sum_{i = 0..k} binomial(n, floor((n-k)/2)+i).
T(n,k) = T(n-1,k-1)+T(n-1,k+1), for all n>=2 and 1<=k<=n-2.
EXAMPLE
n | k=0 1 2 3 4 5 6 7
---+---------------------------------------
0 | 1
1 | 1 2
2 | 2 3 4
3 | 3 6 7 8
4 | 6 10 14 15 16
5 | 10 20 25 30 31 32
6 | 20 35 50 56 62 63 64
7 | 35 70 92 112 119 126 127 128
MAPLE
a:=(n, k)->sum(binomial(n, floor((1/2)*(n-k))+i), i = 0..k):
seq(seq(a(n, k), k = 0..n), n = 0..11);
PROG
(Python)
from math import comb
def A375659(n, k):
return sum(comb(n, i+(n-k)//2) for i in range(k+1)) # John Tyler Rascoe, Sep 04 2024
CROSSREFS
T(n,0) = T(n-1,1) = A001405(n).
T(n,n) = A000079(n).
T(n,n-1) = A000225(n).
T(n,n-2) = A000918(n).
T(n,n-3) = A000247(n).
T(n,n-4) = A052515(n).
Row sums = A189162(n+1).
Sequence in context: A317533 A360999 A343299 * A231227 A231441 A284199
KEYWORD
nonn,tabl,easy
AUTHOR
Marilena Jianu, Aug 23 2024
STATUS
approved