%I A005322 M2799
%S A005322 1,3,9,25,69,189,518,1422,3915,10813,29964,83304,232323,649845,1822824,
%T A005322 5126520,14453451,40843521,115668105,328233969,933206967,2657946907,7583013474
%N A005322 Column of Motzkin triangle.
%C A005322 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 (deutsch(AT)duke.poly.edu), Dec 26 2003
%C A005322 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 (callan(AT)stat.wisc.edu), Jun 07 
               2006
%C A005322 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 (deutsch(AT)duke.poly.edu), 
               Jul 27 2006
%D A005322 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A005322 R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series 
               A, 23 (1977), 291-301.
%F A005322 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 A005322 G.f.=2(1-z-q)/(1-z+q)^2, where q=sqrt(1-2z-3z^2). - Emeric Deutsch (deutsch(AT)duke.poly.edu), 
               Dec 26 2003
%F A005322 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 (deutsch(AT)duke.poly.edu), Jul 27 2006
%F A005322 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 (hoeij(AT)math.fsu.edu), Nov 12 2009]
%p A005322 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 (deutsch(AT)duke.poly.edu), Jul 27 
               2006
%Y A005322 Cf. A026300.
%Y A005322 Cf. A001006.
%Y A005322 A diagonal of triangle A020474.
%Y A005322 Cf. A001006.
%Y A005322 Sequence in context: A094292 A000242 A077846 this_sequence A103780 A098182 
               A007046
%Y A005322 Adjacent sequences: A005319 A005320 A005321 this_sequence A005323 A005324 
               A005325
%K A005322 nonn,new
%O A005322 2,2
%A A005322 N. J. A. Sloane (njas(AT)research.att.com).