A094286 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, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2187, 5787, 15435, 41419, 111659, 302059, 819243, 2226219, 6058155, 16503211, 44991659, 122727595, 334914219, 914235051, 2496201387, 6816678571, 18617371307, 50851322539, 138903833259, 379443202731, 1036559854251

Offset

0,3

Comments

a(n) is the number of Motzkin n-paths of height <= 4. - Alois P. Heinz, Nov 24 2023

Links

Table of n, a(n) for n=0..30.

S. Felsner and D. Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.

Daniel Heldt, On the mixing time of the face flip-and up/down Markov chain for some families of graphs, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.

Index entries for linear recurrences with constant coefficients, signature (5,-6,-2,4).

Formula

a(n) = (1/12)*(4 + 3*2^n + (1-sqrt(3))^n + (1+sqrt(3))^n).

a(n) = 1/3 + 2^(n-2) + A026150(n)/6.

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

Mathematica

LinearRecurrence[{5, -6, -2, 4}, {1, 2, 4, 9}, 30] (* Harvey P. Dale, Feb 01 2012 *)

Crossrefs

Cf. A001006.

Sequence in context: A005207 A257519 A257387 * A094287 A094288 A168051

Adjacent sequences: A094283 A094284 A094285 * A094287 A094288 A094289

Keyword

easy,nonn

Author

Herbert Kociemba, Jun 02 2004

Extensions

a(0)=1 prepended by Alois P. Heinz, Nov 24 2023

Status

approved