|
%I #77 Oct 09 2022 21:24:08
%S 1,4,1,17,8,1,76,50,12,1,354,288,99,16,1,1704,1605,700,164,20,1,8421,
%T 8824,4569,1376,245,24,1,42508,48286,28476,10318,2380,342,28,1,218318,
%U 264128,172508,72128,20180,3776,455,32,1,1137400,1447338
%N Triangle of numbers arising in enumeration of walks on cubic lattice.
%C 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
%C 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
%C 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
%C 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
%C 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
%C 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
%H G. C. Greubel, <a href="/A052179/b052179.txt">Table of n, a(n) for the first 100 rows, flattened</a>
%H Rigoberto Flórez, Leandro Junes, José L. Ramírez, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Florez/florez4.html">Further Results on Paths in an n-Dimensional Cubic Lattice</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.2.
%H R. K. Guy, Catwalks, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Sandsteps and Pascal Pyramids</a>, J. Integer Seqs., Vol. 3 (2000), #00.1.6.
%F Sum_{k>=0} T(m, k)*T(n, k) = T(m+n, 0) = A005572(m+n). - _Philippe Deléham_, Sep 15 2005
%F 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
%F Sum_{k=0..n} T(n,k) = A005573(n). - _Philippe Deléham_, Feb 04 2007
%F Sum_{k=0..n} T(n,k)*(k+1) = 6^n. - _Philippe Deléham_, Mar 27 2007
%F 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
%F As an infinite lower triangular matrix = the binomial transform of A091965 and 4th binomial transform of A053121. - _Gary W. Adamson_, Aug 03 2011
%F G.f.: 2/(1 - 4*x - 2*x*y + sqrt(1 - 8*x + 12*x^2)). - _Daniel Checa_, Aug 17 2022
%F 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
%e Triangle begins:
%e 1;
%e 4, 1;
%e 17, 8, 1;
%e 76, 50, 12, 1;
%e 354, 288, 99, 16, 1;
%e ...
%e Production matrix begins:
%e 4, 1;
%e 1, 4, 1;
%e 0, 1, 4, 1;
%e 0, 0, 1, 4, 1;
%e 0, 0, 0, 1, 4, 1;
%e 0, 0, 0, 0, 1, 4, 1;
%e 0, 0, 0, 0, 0, 1, 4, 1;
%e - _Philippe Deléham_, Nov 04 2011
%p T:= proc(n, k) option remember; `if`(min(n, k)<0, 0,
%p `if`(max(n, k)=0, 1, T(n-1, k-1)+4*T(n-1, k)+T(n-1, k+1)))
%p end:
%p seq(seq(T(n,k), k=0..n), n=0..10); # _Alois P. Heinz_, Oct 28 2021
%t 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_ *)
%Y Cf. A039598, A053121, A064189, A091965.
%K nonn,walk,tabl,easy,nice
%O 0,2
%A _N. J. A. Sloane_, Jan 26 2000
|
