OFFSET
2,2
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.
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
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved