%I #25 Nov 24 2023 14:32:20
%S 1,1,2,4,9,21,51,127,323,835,2187,5787,15435,41419,111659,302059,
%T 819243,2226219,6058155,16503211,44991659,122727595,334914219,
%U 914235051,2496201387,6816678571,18617371307,50851322539,138903833259,379443202731,1036559854251
%N Number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 1, s(n) = 1.
%C a(n) is the number of Motzkin n-paths of height <= 4. - _Alois P. Heinz_, Nov 24 2023
%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 Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (5,-6,-2,4).
%F a(n) = (1/12)*(4 + 3*2^n + (1-sqrt(3))^n + (1+sqrt(3))^n).
%F a(n) = 1/3 + 2^(n-2) + A026150(n)/6.
%F G.f.: -x*(1-3*x+3*x^3) / ( (x-1)*(2*x-1)*(2*x^2+2*x-1) ). - _R. J. Mathar_, Dec 20 2011
%t LinearRecurrence[{5,-6,-2,4},{1,2,4,9},30] (* _Harvey P. Dale_, Feb 01 2012 *)
%Y Cf. 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