A005322 Column of Motzkin triangle.

1, 3, 9, 25, 69, 189, 518, 1422, 3915, 10813, 29964, 83304, 232323, 649845, 1822824, 5126520, 14453451, 40843521, 115668105, 328233969, 933206967, 2657946907, 7583013474, 21668135850, 62007732605, 177696228411, 509899901553, 1464990733969, 4214045993925

Offset: 2

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Number of returns (i.e., down steps hitting the x-axis) in all Motzkin paths of length n. E.g., a(4)=9 because in the nine Motzkin paths of length 4, HHHH, HHU(D), HU(D)H, HUH(D), U(D)HH, U(D)U(D), UH(D)H, UHH(D) and UUD(D), where H=(1,0), U=(1,1), D=(1,-1), we have altogether nine down steps D hitting the x-axis (shown in parentheses). - Emeric Deutsch, Dec 26 2003

Number of nonnegative H,U,D paths of length n that end at height 2. Bijection to the Deutsch manifestation above: turn the last U carrying the path up to height 2 into a D. This gives a Motzkin n-path with a marked return D. - David Callan, Jun 07 2006

Number of Motzkin paths of length n+2, starting with a (1,1) step, ending with a (1,-1) step and touching the x-axis at least three times. Example: a(3)=3 because we have UDHUD, UDUHD and UHDUD, where H=(1,0), U=(1,1), D=(1,-1). - Emeric Deutsch, Jul 27 2006

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• G. C. Greubel, Table of n, a(n) for n = 2..1000
• N. Benyahia Tani, Z. Yahi, and S. Bouroubi, Ordered and non-ordered non-isometric convex quadrilaterals inscribed in a regular n-gon, Bulletin du Laboratoire Liforce, 01 (2014) 1 - 9.
• R. De Castro, A. L. Ramírez and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449 [cs.DM], 2013.
• R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.
• Nickolas Hein and Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
• Stephan Mertens, Exact site-percolation probability on the square lattice, J. Phys. A: Math. Theor., 55 (2022), 334002. See Eq. (9) and Appendix A.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, Une méthode pour obtenir la fonction génératrice d'une série, FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics; arXiv:0912.0072 [math.NT], 2009.

Crossrefs

Cf. A026300, A001006.

A diagonal of triangle A020474.

Programs

Maple

M:=(1-z-sqrt(1-2*z-3*z^2))/2/z^2: ser:=series(z^2*M^3,z=0,35): seq(coeff(ser,z,n),n=2..28); # Emeric Deutsch, Jul 27 2006

Mathematica

CoefficientList[Series[2*(1 - x - Sqrt[1 - 2*x - 3*x^2])/(1 - x + Sqrt[1 - 2*x - 3*x^2])^2, {x,0,50}], x] (* G. C. Greubel, Mar 03 2017 *)

Maxima

a(n):=sum((k-2)*k*sum(binomial(-k+2*j-1,j-1)*(-1)^(n+2-j)*binomial(n+2,j),j,k,n+2),k,1,n+2)/(n+2); /* Vladimir Kruchinin, Sep 26 2011 */

PARI

x='x+O('x^50); Vec(2*(1 - x - sqrt(1 - 2*x - 3*x^2))/(1 - x + sqrt(1 - 2*x - 3*x^2))^2) \\ G. C. Greubel, Mar 03 2017

Formula

a(n) = number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer and |s(i) - s(i-1)| <= 1 for i = 1, 2, ..., n, s(0) = 0, s(n) = 2.

G.f.: 2(1-z-q)/(1-z+q)^2, where q=sqrt(1-2z-3z^2). - Emeric Deutsch, Dec 26 2003

G.f.: z^2*M^3, where M=1+zM+z^2*M^2 is the g.f. of the Motzkin numbers (A001006). - Emeric Deutsch, Jul 27 2006

a(n) = -sqrt(-3)*(-1)^n*(3*n*(13*n+27)*hypergeom([1/2, n],[1],4/3) -hypergeom([1/2, n+1],[1],4/3)*(41*n^2+115*n+60))/(2*(n+3)*(n+5)*(n+6)). - Mark van Hoeij, Nov 12 2009

a(n) = sum(k=1..n+2, (k-2)*k*sum(j=k..n+2, C(-k+2*j-1,j-1)*(-1)^(n+2-j) * C(n+2,j)))/(n+2). - Vladimir Kruchinin, Sep 26 2011

D-finite with recurrence a(n)*(4+n) = (9 + 4*n) a(n-1) - (n-1)*a(n-2) - 6*(n-1)*a(n-3). - Simon Plouffe, Feb 09 2012, corrected for offset Aug 17 2022

a(n) ~ 3^(n + 5/2) / (2*sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 17 2019

D-finite with recurrence -(n+4)*(n-2)*a(n) +n*(2*n+1)*a(n-1) +3*n*(n-1)*a(n-2)=0. - R. J. Mathar, Aug 17 2022