

A208674


Number of words, either empty or beginning with the first letter of the nary alphabet, where each letter of the alphabet occurs 3 times and letters of neighboring word positions are equal or neighbors in the alphabet.


2



1, 1, 10, 37, 163, 640, 2503, 9559, 36154, 135541, 505279, 1875592, 6941035, 25629211, 94478338, 347857921, 1279622611, 4704064120, 17284247263, 63484653151, 233114307274, 855817783741, 3141437229271, 11529935743528, 42314502514051, 155283277278547
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Also the number of (3*n1)step walks on ndimensional cubic lattice from (1,0,...,0) to (3,3,...,3) with positive unit steps in all dimensions such that the absolute difference of the dimension indices used in consecutive steps is <= 1.


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (5,1,14,2,4)


FORMULA

G.f.: (4*x^4+2*x^3+6*x^24*x+1) / (4*x^52*x^414*x^3x^2+5*x1).


EXAMPLE

a(2) = 10 = {aaabbb, aababb, aabbab, aabbba, abaabb, ababab, ababba, abbaab, abbaba, abbbaa} with binary alphabet {a,b}.
a(3) = 37 = {aaabbbccc, aaabbcbcc, aaabbccbc, aaabbcccb, aaabcbbcc, aaabcbcbc, aaabcbccb, aaabccbbc, aaabccbcb, aaabcccbb, aababbccc, aababcbcc, aababccbc, aababcccb, aabbabccc, aabbcccba, aabcbabcc, aabcbccba, aabccbabc, aabccbcba, aabcccbab, aabcccbba, abaabbccc, abaabcbcc, abaabccbc, abaabcccb, abababccc, ababcccba, abbaabccc, abbcccbaa, abcbaabcc, abcbccbaa, abccbaabc, abccbcbaa, abcccbaab, abcccbaba, abcccbbaa} with ternary alphabet {a,b,c}.


MAPLE

a:= n> (Matrix(5, (i, j)> `if`(i=j1, 1, `if`(i=5, [4, 2,
14, 1, 5][j], 0)))^n. <<1, 1, 10, 37, 163>>)[1, 1]:
seq(a(n), n=0..30);


CROSSREFS

Row n=3 of A208673.
Sequence in context: A116970 A199208 A110528 * A137280 A071261 A129426
Adjacent sequences: A208671 A208672 A208673 * A208675 A208676 A208677


KEYWORD

nonn,walk,easy


AUTHOR

Alois P. Heinz, Feb 29 2012


STATUS

approved



