login
A208880
Number of words either empty or beginning with the first letter of the cyclic n-ary alphabet, where each letter of the alphabet occurs twice and letters of neighboring word positions are equal or neighbors in the alphabet.
2
1, 1, 3, 30, 62, 114, 202, 346, 582, 966, 1590, 2602, 4242, 6898, 11198, 18158, 29422, 47650, 77146, 124874, 202102, 327062, 529254, 856410, 1385762, 2242274, 3628142, 5870526, 9498782, 15369426, 24868330, 40237882, 65106342, 105344358, 170450838, 275795338
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}.
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
Row n=2 of A208879.
Sequence in context: A095045 A061472 A132084 * A012009 A001800 A152767
KEYWORD
nonn,walk,easy
AUTHOR
Alois P. Heinz, Mar 02 2012
STATUS
approved