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,2

Links

Table of n, a(n) for n=0..29.

Index entries for linear recurrences with constant coefficients, signature (1, 4).

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.

Example

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.

Mathematica

CoefficientList[Series[(1 + 5 x + 5 x^2)/(1 - x - 4 x^2), {x, 0, 29}], x] (* Michael De Vlieger, Oct 07 2016 *)

Prog

(PARI) Vec((1+5*x+5*x^2)/(1-x-4*x^2) + O(x^40)) \\ Michel Marcus, Oct 06 2016

Crossrefs

Cf. A277236.

Sequence in context: A271545 A272258 A192308 * A171159 A273562 A273748

Adjacent sequences: A277234 A277235 A277236 * A277238 A277239 A277240

Keyword

nonn,easy

Author

Stefan Hollos, Oct 06 2016

Status

approved