|
| |
|
|
A005322
|
|
Column of Motzkin triangle.
(Formerly M2799)
|
|
7
| |
|
|
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; 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 alltogether 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
| R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.
S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures</a>, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
S. Plouffe, < a href="http://arxiv.org/ftp/arxiv/papers/0912/0912.0072.pdf"> Une méthode pour obtenir la fonction génératrice d'une série. FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
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)). [From 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). [From 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]
|
|
|
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
|
|
|
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) [From Vladimir Kruchinin, Sep, 26 2011]
|
|
|
CROSSREFS
| Cf. A026300.
Cf. A001006.
A diagonal of triangle A020474.
Cf. A001006.
Sequence in context: A201533 A000242 A077846 * A103780 A206727 A098182
Adjacent sequences: A005319 A005320 A005321 * A005323 A005324 A005325
|
|
|
KEYWORD
| nonn,changed
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
