|
| |
|
|
A005322
|
|
Column of Motzkin triangle.
(Formerly M2799)
|
|
9
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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, 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, Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
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.
|
|
|
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
a(n)*(5+n) = (13 + 4*n) a(n-1) - n*a(n-2) - 6*n*a(n-3). - Simon Plouffe, Feb 09 2012
a(n) ~ 3^(n + 5/2) / (2*sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 17 2019
|
|
|
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
|
Cf. A026300, A001006.
A diagonal of triangle A020474.
Sequence in context: A201533 A000242 A077846 * A103780 A211288 A206727
Adjacent sequences: A005319 A005320 A005321 * A005323 A005324 A005325
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
STATUS
|
approved
|
| |
|
|
