OFFSET
0,2
COMMENTS
Triangle T(n,k), 0 <= k <= n, read by rows given by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = 4*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + 4*T(n-1,k) + T(n-1,k+1) for k >= 1. - Philippe Deléham, Mar 27 2007
Triangle read by rows: T(n,k) = number of lattice paths from (0,0) to (n,k) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and four types of steps H=(1,0); example: T(3,1)=50 because we have UDU, UUD, 16 HHU paths, 16 HUH paths and 16 UHH paths. - Philippe Deléham, Sep 25 2007
This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k < 0 or if k > n, T(n,0) = x*T(n-1,0) + T(n-1,1), T(n,k) = T(n-1,k-1) + y*T(n-1,k) + T(n-1,k+1) for k >= 1. Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0)-> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; (1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906. - Philippe Deléham, Sep 25 2007
Riordan array ((1-4x-sqrt(1-8x+12x^2))/(2x^2), (1-4x-sqrt(1-8x+12x^2))/(2x)). Inverse of A159764. - Paul Barry, Apr 21 2009
6^n = (n-th row terms) dot (first n+1 terms in (1,2,3,...)). Example: 6^3 = 216 = (76, 50, 12, 1) dot (1, 2, 3, 4) = (76 + 100 + 36 + 4) = 216. - Gary W. Adamson, Jun 15 2011
A subset of the "family of triangles" (Deléham comment of Sep 25 2007) is the succession of binomial transforms beginning with triangle A053121, (0,0); giving -> A064189, (1,1); -> A039598, (2,2); -> A091965, (3,3); -> A052179, (4,4); -> A125906, (5,5) ->, etc.; generally the binomial transform of the triangle generated from (n,n) = that generated from ((n+1),(n+1)). - Gary W. Adamson, Aug 03 2011
LINKS
G. C. Greubel, Table of n, a(n) for the first 100 rows, flattened
Rigoberto Flórez, Leandro Junes, José L. Ramírez, Further Results on Paths in an n-Dimensional Cubic Lattice, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.2.
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6.
FORMULA
Sum_{k>=0} T(m, k)*T(n, k) = T(m+n, 0) = A005572(m+n). - Philippe Deléham, Sep 15 2005
n-th row = M^n * V, where M = the infinite tridiagonal matrix with all 1's in the super and subdiagonals and (4,4,4,...) in the main diagonal. E.g., Row 3 = (76, 50, 12, 1) since M^3 * V = [76, 50, 12, 1, 0, 0, 0, ...]. - Gary W. Adamson, Nov 04 2006
Sum_{k=0..n} T(n,k) = A005573(n). - Philippe Deléham, Feb 04 2007
Sum_{k=0..n} T(n,k)*(k+1) = 6^n. - Philippe Deléham, Mar 27 2007
Sum_{k=0..n} T(n,k)*x^k = A033543(n), A064613(n), A005572(n), A005573(n) for x = -2, -1, 0, 1 respectively. - Philippe Deléham, Nov 28 2009
As an infinite lower triangular matrix = the binomial transform of A091965 and 4th binomial transform of A053121. - Gary W. Adamson, Aug 03 2011
G.f.: 2/(1 - 4*x - 2*x*y + sqrt(1 - 8*x + 12*x^2)). - Daniel Checa, Aug 17 2022
G.f. for the m-th column: x^m*(A(x))^(m+1), where A(x) is the g.f. of the sequence counting the walks on the cubic lattice starting and finishing on the xy plane and never going below it (A005572). Explicitly, the g.f. is x^m*((1 - 4*x - sqrt(1 - 8*x + 12*x^2))/(2*x^2))^(m+1). - Daniel Checa, Aug 28 2022
EXAMPLE
Triangle begins:
1;
4, 1;
17, 8, 1;
76, 50, 12, 1;
354, 288, 99, 16, 1;
...
Production matrix begins:
4, 1;
1, 4, 1;
0, 1, 4, 1;
0, 0, 1, 4, 1;
0, 0, 0, 1, 4, 1;
0, 0, 0, 0, 1, 4, 1;
0, 0, 0, 0, 0, 1, 4, 1;
- Philippe Deléham, Nov 04 2011
MAPLE
T:= proc(n, k) option remember; `if`(min(n, k)<0, 0,
`if`(max(n, k)=0, 1, T(n-1, k-1)+4*T(n-1, k)+T(n-1, k+1)))
end:
seq(seq(T(n, k), k=0..n), n=0..10); # Alois P. Heinz, Oct 28 2021
MATHEMATICA
t[0, 0] = 1; t[n_, k_] /; k < 0 || k > n = 0; t[n_, 0] := t[n, 0] = 4*t[n-1, 0] + t[n-1, 1]; t[n_, k_] := t[n, k] = t[n-1, k-1] + 4*t[n-1, k] + t[n-1, k+1]; Flatten[ Table[t[n, k], {n, 0, 9}, {k, 0, n}]] (* Jean-François Alcover, Oct 10 2011, after _Philippe Deleham_ *)
CROSSREFS
KEYWORD
AUTHOR
N. J. A. Sloane, Jan 26 2000
STATUS
approved