OFFSET
1,5
COMMENTS
Also the number of directed Hamiltonian cycles in the graph on n vertices {1,...,n}, with i adjacent to j iff 2 <= |i-j| <= 3.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1).
FORMULA
G.f.: (3*x^5-2*x^4+x-1)*x / (x^5+x-1).
a(n) = 2*A017899(n-5) for n>=5.
EXAMPLE
For n = 10 the a(10) = 2 permutations are (1,3,6,9,7,10,8,5,2,4), (1,4,2,5,8,10,7,9,6,3).
MAPLE
a:= n-> `if`(n<2, n, (Matrix (5, (i, j)-> `if`(j-i=1 or i=5 and j in {1, 5}, 1, 0))^n. <<2, -2, (0$3)>>)[1, 1]): seq(a(n), n=1..60);
MATHEMATICA
Join[{1}, LinearRecurrence[{1, 0, 0, 0, 1}, {0, 0, 0, 2, 0}, 60]] (* Jean-François Alcover, Oct 28 2021 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Nov 28 2010
STATUS
approved