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
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 Deléham, 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 Deléham, 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 Deléham, Sep 25 2007

Equals binomial transform of triangle A053121. [Gary W. Adamson, Oct 25 2008]

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

REFERENCES

See A026300 for additional 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

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, Idempotent Statistics of the Motzkin and Jones Monoids, arXiv preprint arXiv:1507.04838 [math.CO], 2015.

I. Dolinka, J. East, R. D. Gray, Motzkin monoids and partial Brauer monoids, arXiv preprint arXiv:1512.02279 [math.GR], 2015.

Donatella Merlini, Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.

R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 265.

Sheng-Liang Yang, Yan-Ni Dong, and Tian-Xiao He, Some matrix identities on colored Motzkin paths, Discrete Mathematics 340.12 (2017): 3081-3091.

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 Deléham, 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 Deléham, Apr 21 2007

T(n,k) = k/n*sum(j=0..n, binomial(n,j)*binomial(j,2*j-n-k)). [Vladimir Kruchinin, Feb 12 2011]

Sum_{k=0..n} T(n,k)*(-1)^k*(k+1) = (-1)^n. - Werner Schulte, Jul 08 2015

Sum_{k=0..n} T(n,k)*(k+1)^3 = (2*n+1)*3^n. - Werner Schulte, Jul 08 2015

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

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

[Philippe Deléham, Nov 04 2011]

MATHEMATICA

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 *)

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

(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 */

CROSSREFS

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

Cf. A001006, A002026, A005322, A005323.

Cf. A053121. - Gary W. Adamson, Oct 25 2008

Sequence in context: A105306 A183191 A273713 * A273897 A063415 A098977

Adjacent sequences:  A064186 A064187 A064188 * A064190 A064191 A064192

KEYWORD

nonn,easy,tabl

AUTHOR

N. J. A. Sloane, Sep 21 2001

EXTENSIONS

More terms from Vladeta Jovovic, Sep 23 2001

STATUS

approved

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 November 14 17:12 EST 2018. Contains 317210 sequences. (Running on oeis4.)