

A208880


Number of words either empty or beginning with the first letter of the cyclic nary 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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*n1)step walks on ndimensional 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^610*x^522*x^4+24*x^3+2*x^22*x+1)/((x^2+x1)*(x1)^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*(n1),
(<<0100>, <0010>, <0001>, <1123>>^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
Adjacent sequences: A208877 A208878 A208879 * A208881 A208882 A208883


KEYWORD

nonn,walk,easy


AUTHOR

Alois P. Heinz, Mar 02 2012


STATUS

approved



