login
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.
1

%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