login
Number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 7 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 1, s(n) = 1.
0

%I #26 Nov 24 2023 14:30:36

%S 1,1,2,4,9,21,51,127,323,835,2188,5798,15510,41822,113531,309937,

%T 850118,2340918,6466953,17913087,49726649,138287113,385126811,

%U 1073832695,2996974774,8370739326,23394528640,65415732100,182989086965,512046072481,1433197869570

%N Number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 7 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} 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, m=7.

%C a(n) is the number of Motzkin n-paths of height <= 5. - _Alois P. Heinz_, Nov 24 2023

%H S. Felsner, 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) = (2/7)*Sum_{k=1..6} sin(Pi*k/7)^2(1+2*cos(Pi*k/7))^n.

%F Conjecture: a(n)= +6*a(n-1) -10*a(n-2) +9*a(n-4) -2*a(n-5) -a(n-6) with g.f. -x*(-1+4*x-2*x^2-5*x^3+2*x^4+x^5) / ( (x^3+3*x^2-4*x+1)*(x^3-x^2-2*x+1) ). - _R. J. Mathar_, Dec 20 2011

%t f[n_] := FullSimplify[ TrigToExp[(2/7)*Sum[ Sin[Pi*k/7]^2(1 + 2Cos[Pi*k/7])^n, {k, 1, 6}]]]; Table[ f[n], {n, 28}] (* _Robert G. Wilson v_, Jun 18 2004 *)

%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