|
| |
|
|
A064189
|
|
Triangle T(n,k), 0<=k<=n, read by rows, defined by: T(0,0)=1, T(n,k)= 0 if n<k, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,k+1).
|
|
36
|
|
|
|
1, 1, 1, 2, 2, 1, 4, 5, 3, 1, 9, 12, 9, 4, 1, 21, 30, 25, 14, 5, 1, 51, 76, 69, 44, 20, 6, 1, 127, 196, 189, 133, 70, 27, 7, 1, 323, 512, 518, 392, 230, 104, 35, 8, 1, 835, 1353, 1422, 1140, 726, 369, 147, 44, 9, 1, 2188, 3610, 3915, 3288, 2235, 1242, 560, 200, 54, 10, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Motzkin triangle read in reverse order.
T(n,k) = number of lattice paths from (0,0) to (n,k), staying weakly above the x-axis and consisting of steps U=(1,1), D=(1,-1) and H=(1,0). Example: T(3,1) = 5 because we have HHU, UDU, HUH, UHH and UUD. Columns 0,1,2 and 3 give A001006 (Motzkin numbers), A002026 (first differences of Motzkin numbers), A005322 and A005323, respectively. - Emeric Deutsch, Feb 29 2004
Riordan array ((1-x-sqrt(1-2x-3x^2))/(2x^2), (1-x-sqrt(1-2x-3x^2))/(2x)). Inverse is the array (1/(1+x+x^2), x/(1+x+x^2)) (A104562). - Paul Barry, Mar 15 2005
Inverse binomial matrix applied to A039598 . - Philippe DELEHAM, Feb 28 2007
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)=T(n-1,0)+T(n-1,1), T(n,k)=T(n-1,k-1)+T(n-1,k)+T(n-1,k+1) for k>=1 . - Philippe DELEHAM, Mar 27 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 DELEHAM, Sep 25 2007
Equals binomial transform of triangle A053121 [From Gary W. Adamson, Oct 25 2008]
Contribution from Johannes W. Meijer, Oct 10 2010: (Start)
Consider a semi-infinite chessboard with squares labeled (n,k), ranks or rows n >= 0, files or columns k >= 0; the number of king-paths of length n from (0,0) to (n,k), 0 <= k <= n, is T(n,k). The recurrence relation given above relates to the movements of the king. This is essentially the comment made by Harrie Grondijs for the Motzkin triangle A026300. (End)
|
|
|
REFERENCES
|
See A026300 for references and other information.
E. Barcucci, R. Pinzani, R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.
|
|
|
LINKS
|
Table of n, a(n) for n=0..65.
|
|
|
FORMULA
|
Sum_{k=0..n} T(n, k)*(k+1) = 3^n.
Sum_{k=0..n} T(n, k)*T(n, n-k) = T(2*n, n) -T(2*n, n+2)
G.f.: M/(1-t*z*M), where M=1+z*M+z^2*M^2 is the g.f. of the Motzkin numbers (A001006). - Emeric Deutsch, Feb 29 2004
Sum_{k>=0} T(m, k)*T(n, k) = A001006(m+n) . - Philippe Deléham, Mar 05 2004
Sum_{k>=0} T(n-k, k) = A005043(n+2) . - Philippe DELEHAM, May 31 2005
Column k has e.g.f. exp(x)*(BesselI(k,2*x)-BesselI(k+2,2*x)); - Paul Barry, Feb 16 2006
T(n,k)=sum{j=0..n, C(n,j)*(C(n-j,j+k)-C(n-j,j+k+2))}; - Paul Barry, Feb 16 2006
n-th row is generated from M^n * V, where M = the infinite tridiagonal matrix with all 1's in the super, main and subdiagonals; and V = the infinite vector [1,0,0,0...]. E.g. Row 3 = (4, 5, 3, 1), since M^3 * V = [4, 5, 3, 1, 0, 0, 0...]. - Gary W. Adamson, Nov 04 2006
T(n,k)=A122896(n+1,k+1) . - Philippe DELEHAM, Apr 21 2007
T(n,k)=k/n*sum(j=0..n, binomial(n,j)*binomial(j,2*j-n-k)), [From Vladimir Kruchinin, Feb 12 2011]
|
|
|
EXAMPLE
|
Triangle begins:
1;
1,1;
2,2,1;
4,5,3,1;
9,12,9,4,1; ...
Production matrix begins :
1, 1
1, 1, 1
0, 1, 1, 1
0, 0, 1, 1, 1
0, 0, 0, 1, 1, 1
0, 0, 0, 0, 1, 1, 1
0, 0, 0, 0, 0, 1, 1, 1
[From Philippe Deléham, Nov 04 2011]
|
|
|
PROG
|
(Sage)
def A064189_triangel(dim):
M = matrix(SR, dim, dim)
for n in range(dim): M[n, n] = 1
for n in (1..dim-1):
for k in (0..n-1):
M[n, k] = M[n-1, k-1]+M[n-1, k]+M[n-1, k+1]
return M
A064189_triangel(9) # Peter Luschny, Sep 20 2012
|
|
|
CROSSREFS
|
Triangle in A026300 (the main entry for this sequence) with rows read in reverse order.
Cf. A001006, A002026, A005322, A005323.
A053121 [From Gary W. Adamson, Oct 25 2008]
Sequence in context: A202193 A105306 A183191 * A063415 A098977 A113547
Adjacent sequences: A064186 A064187 A064188 * A064190 A064191 A064192
|
|
|
KEYWORD
|
nonn,easy,tabl,changed
|
|
|
AUTHOR
|
N. J. A. Sloane, Sep 21 2001
|
|
|
EXTENSIONS
|
More terms from Vladeta Jovovic, Sep 23 2001
|
|
|
STATUS
|
approved
|
| |
|
|
