OFFSET
1,3
COMMENTS
Comments from David Callan, Jul 15 2004: "a(n+1) is the number of Motzkin (2n)-paths whose longest level segment has length n. (A level segment is a maximal sequence of contiguous flatsteps.) Example: with n=3, the paths counted by a(4) are FFFUDF, FFFUFD, FUDFFF, FUFFFD, UFDFFF, UFFFDF. Here is a bijection to the sequences (s(i)) above.
"Given such a Motzkin (2n)-path, delete the (unique) longest level segment to split the path into A,B. Form the path BUA (U can be recovered as the up step immediately following the rightmost of the lowest points on this path). This path will not start or end with F.
"Transfer the level segment (if any) following the first step to the end. Code the resulting path with 1 for U, 0 for F and -1 for D. Then take partial sums (including the empty sum) to get a sequence (s(i)). Example: UF^9UFFUDDDF -> U,UFFUDDDF -> UFFUDDDFUU -> UUDDDFUUFF -> 1,1,-1,-1,-1,0,1,1,0,0 -> (0,1,2,1,0,-1,-1,0,1,1,1)."
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 1..200
FORMULA
a(n+1)=sum(j=1..n/2, C[n-1, 2j-1] C[2j+1, j]). This sum counts the Motzkin (2n)-paths above by number j of up steps and the sequences (s(i)) by number j of indices i for which s(i) - s(i-1) = -1. GF: (1-x)^2 ( (1-x)(1-2x-3x^2)^(-1/2) - 1 )/(2x). - David Callan, Jul 15 2004
Conjecture: (n+1)*a(n) +(-3*n+2)*a(n-1) +(-n-7)*a(n-2) +3*(n-4)*a(n-3)=0. - R. J. Mathar, Jun 23 2013
a(n) ~ 2 * 3^(n+1/2) / (9 * sqrt(Pi*n)). - Vaclav Kotesovec, Feb 13 2014
MATHEMATICA
Rest[CoefficientList[Series[(1-x)^2*((1-x)*(1-2*x-3*x^2)^(-1/2)-1)/(2*x), {x, 0, 20}], x]] (* Vaclav Kotesovec, Feb 13 2014 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved