A024998 a(n) = number of (s(0), s(1), ..., s(n)) such that every s(i) is an integer, s(0) = 0, |s(i) - s(i-1)| = 1 for i = 1,2; |s(i) - s(i-1)| <= 1 for i >= 3, s(n) = 1. Also a(n) = T(n,n-1), where T is the array defined in A024996.

1, 0, 3, 6, 19, 52, 150, 428, 1232, 3552, 10275, 29790, 86559, 251980, 734773, 2145822, 6275145, 18373296, 53856153, 158025186, 464112297, 1364247180, 4013353932, 11815188000, 34807249134, 102606325136, 302646363725, 893175905778

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

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

Programs

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 *)

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