login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 39

%I

%S 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,

%T 127,196,189,133,70,27,7,1,323,512,518,392,230,104,35,8,1,835,1353,

%U 1422,1140,726,369,147,44,9,1,2188,3610,3915,3288,2235,1242,560,200,54,10,1

%N 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).

%C Motzkin triangle read in reverse order.

%C 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

%C 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

%C Inverse binomial matrix applied to A039598 . - _Philippe Deléham_, Feb 28 2007

%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)=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 Deléham_, Mar 27 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 Equals binomial transform of triangle A053121. [_Gary W. Adamson_, Oct 25 2008]

%C 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. - _Johannes W. Meijer_, Oct 10 2010

%D See A026300 for additional references and other information.

%D E. Barcucci, R. Pinzani, R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.

%H G. C. Greubel, <a href="/A064189/b064189.txt">Table of n, a(n) for the first 50 rows, flattened</a>

%H I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, <a href="http://arxiv.org/abs/1507.04838">Idempotent Statistics of the Motzkin and Jones Monoids</a>, arXiv preprint arXiv:1507.04838 [math.CO], 2015.

%H I. Dolinka, J. East, R. D. Gray, <a href="http://arxiv.org/abs/1512.02279">Motzkin monoids and partial Brauer monoids</a>, arXiv preprint arXiv:1512.02279 [math.GR], 2015.

%H Donatella Merlini, Massimo Nocentini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Merlini/merlini5.html">Algebraic Generating Functions for Languages Avoiding Riordan Patterns</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.

%H R. Pemantle and M. C. Wilson, <a href="http://dx.doi.org/10.1137/050643866">Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 265.

%H Sheng-Liang Yang, Yan-Ni Dong, and Tian-Xiao He, <a href="http://dx.doi.org/10.1016/j.disc.2017.07.006">Some matrix identities on colored Motzkin paths</a>, Discrete Mathematics 340.12 (2017): 3081-3091.

%F Sum_{k=0..n} T(n, k)*(k+1) = 3^n.

%F Sum_{k=0..n} T(n, k)*T(n, n-k) = T(2*n, n) -T(2*n, n+2)

%F 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

%F Sum_{k>=0} T(m, k)*T(n, k) = A001006(m+n) . - _Philippe Deléham_, Mar 05 2004

%F Sum_{k>=0} T(n-k, k) = A005043(n+2) . - _Philippe Deléham_, May 31 2005

%F Column k has e.g.f. exp(x)*(BesselI(k,2*x)-BesselI(k+2,2*x)). - _Paul Barry_, Feb 16 2006

%F 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

%F 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

%F T(n,k) = A122896(n+1,k+1) . - _Philippe Deléham_, Apr 21 2007

%F T(n,k) = k/n*sum(j=0..n, binomial(n,j)*binomial(j,2*j-n-k)). [_Vladimir Kruchinin_, Feb 12 2011]

%F Sum_{k=0..n} T(n,k)*(-1)^k*(k+1) = (-1)^n. - _Werner Schulte_, Jul 08 2015

%F Sum_{k=0..n} T(n,k)*(k+1)^3 = (2*n+1)*3^n. - _Werner Schulte_, Jul 08 2015

%F G.f.: 2 / (1 - x + sqrt(1 - 2*x - 3*x^2) - 2*x*y) = Sum_{n >= k >=0} T(n, k) * x^n * y^k. - _Michael Somos_, Jun 06 2016

%e Triangle begins:

%e 1;

%e 1,1;

%e 2,2,1;

%e 4,5,3,1;

%e 9,12,9,4,1;

%e ...

%e Production matrix begins :

%e 1, 1

%e 1, 1, 1

%e 0, 1, 1, 1

%e 0, 0, 1, 1, 1

%e 0, 0, 0, 1, 1, 1

%e 0, 0, 0, 0, 1, 1, 1

%e 0, 0, 0, 0, 0, 1, 1, 1

%e [_Philippe Deléham_, Nov 04 2011]

%t T[0, 0, x_, y_] := 1; T[n_, 0, x_, y_] := x*T[n - 1, 0, x, y] + T[n - 1, 1, x, y]; T[n_, k_, x_, y_] := T[n, k, x, y] = If[k < 0 || k > n, 0, T[n - 1, k - 1, x, y] + y*T[n - 1, k, x, y] + T[n - 1, k + 1, x, y]]; Table[T[n, k, 1, 1], {n, 0, 10}, {k, 0, n}] // Flatten (* _G. C. Greubel_, Apr 21 2017 *)

%o (Sage)

%o def A064189_triangel(dim):

%o M = matrix(SR,dim,dim)

%o for n in range(dim): M[n,n] = 1

%o for n in (1..dim-1):

%o for k in (0..n-1):

%o M[n,k] = M[n-1,k-1]+M[n-1,k]+M[n-1,k+1]

%o return M

%o A064189_triangel(9) # _Peter Luschny_, Sep 20 2012

%o (PARI) {T(n, k) = if( k<0 || k>n, 0, polcoeff( polcoeff( 2 / (1 - x + sqrt(1 - 2*x - 3*x^2) - 2*x*y) + x * O(x^n), n), k))}; /* _Michael Somos_, Jun 06 2016 */

%Y Triangle in A026300 (the main entry for this sequence) with rows read in reverse order.

%Y Cf. A001006, A002026, A005322, A005323.

%Y Cf. A053121. - _Gary W. Adamson_, Oct 25 2008

%K nonn,easy,tabl

%O 0,4

%A _N. J. A. Sloane_, Sep 21 2001

%E More terms from _Vladeta Jovovic_, Sep 23 2001

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 17 03:29 EDT 2018. Contains 313810 sequences. (Running on oeis4.)