A236340 Number of length n binary words such that maximal runs of 1's are restricted to length one or two and maximal runs of 0's are of odd length.

1, 2, 3, 5, 7, 13, 19, 33, 51, 85, 135, 221, 355, 577, 931, 1509, 2439, 3949, 6387, 10337, 16723, 27061, 43783, 70845, 114627, 185473, 300099, 485573, 785671, 1271245, 2056915, 3328161, 5385075, 8713237, 14098311, 22811549

Offset

0,2

Links

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

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

Formula

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

a(0)=1, a(1)=2, a(2)=3, a(3)=5, a(4)=7 for n>=5, a(n) = 2*a(n-2) + a(n-3).

a(n) = Fibonacci(n+2) - Fibonacci(n-4) - (-1)^n for n>=2, with Fibonacci(n) = A000045(n). - Greg Dresden, Jul 03 2020

Example

a(4)=7 because we have: 0001, 0101, 0110, 1000, 1010, 1011, 1101.

Mathematica

nn=35; CoefficientList[Series[(1+x+x^2)(1+x/(1-x^2))/(1-(x^2+x^3)/(1-x^2)), {x, 0, nn}], x]
LinearRecurrence[{0, 2, 1}, {1, 2, 3, 5, 7}, 40] (* Harvey P. Dale, Apr 18 2020 *)

Crossrefs

Sequence in context: A075580 A077132 A138184 * A273161 A008965 A113864

Adjacent sequences: A236337 A236338 A236339 * A236341 A236342 A236343

Keyword

nonn

Author

Geoffrey Critzer, Jan 27 2014

Status

approved