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, 36909859, 59721409, 96631267

Offset

0,2

Links

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

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

a(n) = 4*Fibonacci(n-1) - (-1)^n for n>=2. - Ira M. Gessel, Jan 22 2025

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

Cf. A000045.

Sequence in context: A075580 A077132 A138184 * A273161 A008965 A113864

Adjacent sequences: A236337 A236338 A236339 * A236341 A236342 A236343

Keyword

nonn,changed

Author

Geoffrey Critzer, Jan 27 2014

Status

approved