A277236 - OEIS

%I #25 Nov 07 2016 05:07:41

%S 1,4,10,26,66,170,434,1114,2850,7306,18706,47930,122754,314474,805490,

%T 2063386,5285346,13538890,34680274,88835834,227556930,582900266,

%U 1493127986,3824729050,9797240994,25096157194,64285121170,164669749946,421810234626,1080489234410,2767730172914

%N 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.

%C 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.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,4).

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

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

%F 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.

%e 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.

%e 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.

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

%o (PARI) Vec((1+3*z+2*z^2)/(1-z-4*z^2) + O(z^40)) \\ _Michel Marcus_, Oct 06 2016

%Y Cf. A222132 (z1), A277237.

%K nonn,easy

%O 0,2

%A _Stefan Hollos_, Oct 06 2016