|
%I M2799 #70 Sep 12 2023 12:07:32
%S 1,3,9,25,69,189,518,1422,3915,10813,29964,83304,232323,649845,
%T 1822824,5126520,14453451,40843521,115668105,328233969,933206967,
%U 2657946907,7583013474,21668135850,62007732605,177696228411,509899901553,1464990733969,4214045993925
%N Column of Motzkin triangle.
%C 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
%C 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
%C 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
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H G. C. Greubel, <a href="/A005322/b005322.txt">Table of n, a(n) for n = 2..1000</a>
%H N. Benyahia Tani, Z. Yahi, and S. Bouroubi, <a href="https://liforce.usthb.dz/sites/default/files/2020-11/article1.pdf">Ordered and non-ordered non-isometric convex quadrilaterals inscribed in a regular n-gon</a>, Bulletin du Laboratoire Liforce, 01 (2014) 1 - 9.
%H R. De Castro, A. L. Ramírez and J. L. Ramírez, <a href="http://arxiv.org/abs/1310.2449">Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs</a>, arXiv preprint arXiv:1310.2449 [cs.DM], 2013.
%H R. Donaghey and L. W. Shapiro, <a href="http://dx.doi.org/10.1016/0097-3165(77)90020-6">Motzkin numbers</a>, J. Combin. Theory, Series A, 23 (1977), 291-301.
%H Nickolas Hein and Jia Huang, <a href="https://arxiv.org/abs/1807.04623">Variations of the Catalan numbers from some nonassociative binary operations</a>, arXiv:1807.04623 [math.CO], 2018.
%H Stephan Mertens, <a href="https://doi.org/10.1088/1751-8121/ac4195">Exact site-percolation probability on the square lattice</a>, J. Phys. A: Math. Theor., 55 (2022), 334002. See Eq. (9) and Appendix A.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0912.0072">Une méthode pour obtenir la fonction génératrice d'une série</a>, FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics; arXiv:0912.0072 [math.NT], 2009.
%F 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.
%F G.f.: 2(1-z-q)/(1-z+q)^2, where q=sqrt(1-2z-3z^2). - _Emeric Deutsch_, Dec 26 2003
%F 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
%F 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
%F 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
%F 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
%F a(n) ~ 3^(n + 5/2) / (2*sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Sep 17 2019
%F 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
%p 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
%t 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 *)
%o (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 */
%o (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
%Y Cf. A026300, A001006.
%Y A diagonal of triangle A020474.
%K nonn
%O 2,2
%A _N. J. A. Sloane_
|
