login
Number of binary strings of length n with no substrings equal to 0000 or 0011.
2

%I #28 Oct 07 2024 06:32:42

%S 1,2,4,8,14,25,45,80,142,253,450,800,1423,2531,4501,8005,14237,25320,

%T 45031,80087,142433,253314,450514,801230,1424971,2534282,4507169,

%U 8015908,14256129,25354235,45091990,80195185,142625502,253656548,451123000,802313060

%N Number of binary strings of length n with no substrings equal to 0000 or 0011.

%H Alois P. Heinz, <a href="/A164388/b164388.txt">Table of n, a(n) for n = 0..2000</a> (first 500 terms from R. H. Hardin)

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

%F G.f.: (x+1)*(x^2+1)/(x^5-x^3-x^2-x+1). - _R. J. Mathar_, Nov 28 2011

%F a(n) = 2^n for n<4, a(4)=14, a(5)=25, a(6)=45, a(7)=80, a(8)=142, a(n)=a(n-1)+a(n-2)+a(n-3)-a(n-5). - _Harvey P. Dale_, Feb 15 2013

%t LinearRecurrence[{1,1,1,0,-1},{14,25,45,80,142},40] (* _Harvey P. Dale_, Feb 15 2013 *)

%K nonn,easy

%O 0,2

%A _R. H. Hardin_, Aug 14 2009

%E Edited by _Alois P. Heinz_, Oct 11 2017