A277236 Number of strings of length n composed of symbols from the circular list [1,2,3,4] 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 and 3.

1, 4, 10, 26, 66, 170, 434, 1114, 2850, 7306, 18706, 47930, 122754, 314474, 805490, 2063386, 5285346, 13538890, 34680274, 88835834, 227556930, 582900266, 1493127986, 3824729050, 9797240994, 25096157194, 64285121170, 164669749946, 421810234626, 1080489234410, 2767730172914

Offset

0,2

Comments

To generalize to strings composed of symbols from the circular list [1,2,3,...2m], m>=2, with no runs of 2 or more allowed for symbols 1,3,5,...2m-1, use the same recurrence given below with initial values a(1)=2m, a(2)=5m, see A277237 for the m=3 case.

Links

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

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

Formula

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

For n>=3, the recurrence is a(n) = a(n-1) + 4*a(n-2), a(1)=4, a(2)=10.

a(n) = ((13+3*sqrt(17))*z1^n-(13-3*sqrt(17))*z2^n)/(4*sqrt(17)) where z1=(1+sqrt(17))/2 and z2=(1-sqrt(17))/2.

Example

For n=3 the 26 strings are 121, 122, 123, 141, 143, 144, 212, 214, 221, 222, 223, 232, 234, 321, 322, 323, 341, 343, 344, 412, 414, 432, 434, 441, 443, 444.
For n=4 the 66 strings are 1212, 1214, 1221, 1222, 1223, 1232, 1234, 1412, 1414, 1432, 1434, 1441, 1443, 1444, 2121, 2122, 2123, 2141, 2143, 2144, 2212, 2214, 2221, 2222, 2223, 2232, 2234, 2321, 2322, 2323, 2341, 2343, 2344, 3212, 3214, 3221, 3222, 3223, 3232, 3234, 3412, 3414, 3432, 3434, 3441, 3443, 3444, 4121, 4122, 4123, 4141, 4143, 4144, 4321, 4322, 4323, 4341, 4343, 4344, 4412, 4414, 4432, 4434, 4441, 4443, 4444.

Mathematica

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

Prog

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

Crossrefs

Cf. A222132 (z1), A277237.

Sequence in context: A178037 A175658 A191605 * A218208 A207095 A126358

Adjacent sequences: A277233 A277234 A277235 * A277237 A277238 A277239

Keyword

nonn,easy

Author

Stefan Hollos, Oct 06 2016

Status

approved