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
Links
- 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).
Crossrefs
Cf. A001006.
Programs
-
Mathematica
LinearRecurrence[{5,-6,-2,4},{1,2,4,9},30] (* Harvey P. Dale, Feb 01 2012 *)
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
Extensions
a(0)=1 prepended by Alois P. Heinz, Nov 24 2023
Comments