%I #30 Nov 24 2023 14:25:03
%S 1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113633,310557,
%T 853333,2355861,6531062,18171848,50722229,141973073,398351055,
%U 1120056347,3155043447,8901325751,25147423616,71127785002,201381834019,570655858439,1618256772285
%N Number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 8 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 1, s(n) = 1.
%C In general, a(n) = (2/m)*Sum_{k=1..m-1} sin(Pi*k/m)^2(1+2*cos(Pi*k/m))^n counts the (s(0), s(1), ..., s(n)) such that 0 < s(i) < m and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 1, s(n) = 1. Here is m=8.
%C a(n) is the number of Motzkin n-paths of height <= 6. - _Alois P. Heinz_, Nov 24 2023
%H Alois P. Heinz, <a href="/A094288/b094288.txt">Table of n, a(n) for n = 0..2203</a>
%H S. Felsner and D. Heldt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Felsner/felsner2.html">Lattice Path Enumeration and Toeplitz Matrices</a>, J. Int. Seq. 18 (2015) # 15.1.3.
%H Daniel Heldt, <a href="http://dx.doi.org/10.14279/depositonce-5182">On the mixing time of the face flip-and up/down Markov chain for some families of graphs</a>, Dissertation, Mathematik und Naturwissenschaften der Technischen Universität Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
%F a(n) = (1/4)*Sum_{k=1..7} sin(Pi*k/8)^2*(1+2*cos(Pi*k/8))^n.
%F Conjecture: a(n)= +7*a(n-1) -15*a(n-2) +5*a(n-3) +15*a(n-4) -9*a(n-5) -3*a(n-6) +a(n-7) with g.f. -x*(1-5*x+5*x^2+6*x^3-7*x^4-2*x^5+x^6) / ( (x-1)*(x^2+2*x-1)*(x^4-4*x^3-2*x^2+4*x-1) ). - _R. J. Mathar_, Dec 20 2011
%t f[n_] := FullSimplify[ TrigToExp[(1/4)*Sum[Sin[Pi*k/8]^2(1 + 2Cos[Pi*k/8])^n, {k, 1, 7}]]]; Table[ f[n], {n, 28}] (* _Robert G. Wilson v_, Jun 18 2004 *)
%Y This is a different sequence from the Motzkin numbers, A001006.
%K easy,nonn
%O 0,3
%A _Herbert Kociemba_, Jun 02 2004
%E a(0)=1 prepended by _Alois P. Heinz_, Nov 24 2023