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

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

Offset: 0

Author

Alois P. Heinz, Feb 29 2012

Keywords

• nonn
• walk
• easy

Comments

Also the number of (3*n-1)-step walks on n-dimensional 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.

Examples

			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}.
		

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)

Crossrefs

Row n=3 of A208673.

Programs

Maple

a:= n-> (Matrix(5, (i, j)-> `if`(i=j-1, 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);

Formula

G.f.: -(4*x^4+2*x^3+6*x^2-4*x+1) / (4*x^5-2*x^4-14*x^3-x^2+5*x-1).