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
Examples
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.
Links
- Index entries for linear recurrences with constant coefficients, signature (1,4).
Programs
-
Mathematica
CoefficientList[Series[(1 + 3 x + 2 x^2)/(1 - x - 4 x^2), {x, 0, 30}], x] (* Michael De Vlieger, Oct 07 2016 *) LinearRecurrence[{1,4},{1,4,10},40] (* Harvey P. Dale, Jul 12 2025 *) -
PARI
Vec((1+3*z+2*z^2)/(1-z-4*z^2) + O(z^40)) \\ Michel Marcus, Oct 06 2016
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.
Comments