login
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.
0

%I #22 Jul 04 2020 03:11:03

%S 1,2,3,5,7,13,19,33,51,85,135,221,355,577,931,1509,2439,3949,6387,

%T 10337,16723,27061,43783,70845,114627,185473,300099,485573,785671,

%U 1271245,2056915,3328161,5385075,8713237,14098311,22811549

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

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

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

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

%F a(n) = Fibonacci(n+2) - Fibonacci(n-4) - (-1)^n for n>=2, with Fibonacci(n) = A000045(n). - _Greg Dresden_, Jul 03 2020

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

%t 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]

%t LinearRecurrence[{0,2,1},{1,2,3,5,7},40] (* _Harvey P. Dale_, Apr 18 2020 *)

%K nonn

%O 0,2

%A _Geoffrey Critzer_, Jan 27 2014