OFFSET
0,3
COMMENTS
The first and the last letters are considered neighbors in a cyclic alphabet. The words are not considered cyclic here.
Also the number of (2*n-1)-step walks on n-dimensional cubic lattice from (1,0,...,0) to (2,2,...,2) with positive unit steps in all dimensions such that the indices of dimensions used in consecutive steps differ by less than 2 or are in the set {1,n}.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).
FORMULA
G.f.: -(11*x^6-10*x^5-22*x^4+24*x^3+2*x^2-2*x+1)/((x^2+x-1)*(x-1)^2).
EXAMPLE
a(0) = 1: the empty word.
a(1) = 1 = |{aa}|.
a(2) = 3 = |{aabb, abab, abba}|.
a(3) = 30 = |{aabbcc, aabcbc, aabccb, aacbbc, aacbcb, aaccbb, ababcc, abacbc, abaccb, abbacc, abbcac, abbcca, abcabc, abcacb, abcbac, abcbca, abccab, abccba, acabbc, acabcb, acacbb, acbabc, acbacb, acbbac, acbbca, acbcab, acbcba, accabb, accbab, accbba}|.
MAPLE
a:= n-> `if`(n<3, 1+n*(n-1),
(<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|-1|-2|3>>^n.
<<2, 2, 14, 30>>)[1, 1]):
seq(a(n), n=0..40);
MATHEMATICA
Join[{1, 1, 3}, LinearRecurrence[{3, -2, -1, 1}, {30, 62, 114, 202}, 40]] (* Harvey P. Dale, Mar 09 2015 *)
CROSSREFS
KEYWORD
nonn,walk,easy
AUTHOR
Alois P. Heinz, Mar 02 2012
STATUS
approved