A277237 Number of strings of length n composed of symbols from the circular list [1,2,3,4,5,6] such that adjacent symbols in the string must be adjacent in the list. No runs of length 2 or more are allowed for symbols 1, 3 and 5.
1, 6, 15, 39, 99, 255, 651, 1671, 4275, 10959, 28059, 71895, 184131, 471711, 1208235, 3095079, 7928019, 20308335, 52020411, 133253751, 341335395, 874350399, 2239691979, 5737093575, 14695861491, 37644235791, 96427681755, 247004624919, 632715351939, 1620733851615
Offset: 0
Examples
For n=2 the 15 strings are: 12, 16, 21, 22, 23, 32, 34, 41, 43, 44, 54, 56, 61, 65, 66. For n=3 the 39 strings are: 121, 122, 123, 161, 165, 166, 212, 216, 221, 222, 223, 232, 234, 321, 322, 323, 341, 343, 344, 412, 416, 432, 434, 441, 443, 444, 541, 543, 544, 561, 565, 566, 612, 616, 654, 656, 661, 665, 666.
Links
- Index entries for linear recurrences with constant coefficients, signature (1, 4).
Crossrefs
Cf. A277236.
Programs
-
Mathematica
CoefficientList[Series[(1 + 5 x + 5 x^2)/(1 - x - 4 x^2), {x, 0, 29}], x] (* Michael De Vlieger, Oct 07 2016 *) -
PARI
Vec((1+5*x+5*x^2)/(1-x-4*x^2) + O(x^40)) \\ Michel Marcus, Oct 06 2016
Formula
G.f.: (1+5*x+5*x^2)/(1-x-4*x^2).
For n>=3, the recurrence is a(n) = a(n-1) + 4*a(n-2), a(1)=6, a(2)=15.
a(n) = 3*((13+3*sqrt(17))*z1^n-(13-3*sqrt(17))*z2^n)/(8*sqrt(17)), where z1=(1+sqrt(17))/2 and z2=(1-sqrt(17))/2.