%I #32 Jun 13 2015 00:53:14

%S 1,2,4,8,13,22,37,62,104,175,294,494,830,1395,2344,3939,6619,11123,

%T 18691,31409,52780,88693,149041,250452,420864,707229,1188441,1997081,

%U 3355934,5639380,9476526,15924546,26759925,44967917,75564988,126980925,213381292

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

%H R. H. Hardin and Harvey P. Dale, <a href="/A164428/b164428.txt">Table of n, a(n) for n = 0..1000</a> (terms n=4..500 from R. H. Hardin)

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

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

%e From _Tom Edgar_, Feb 10 2015: (Start)

%e When n=4, there are 16 binary strings of length 4 and 3 of them are the ones to avoid, so a(4) = 13.

%e When n=5, there are 32 binary strings of length 5; the ones including a substring of the indicated form are '00000', '10000', '00001', '00011', '10011', '00110', '00111', 01001', '11001', and '10010'. Since there are 10 to avoid, we have a(5) = 22.

%e (End)

%t Join[{1,2,4},LinearRecurrence[{1,1,0,1,-1},{8,13,22,37,62},40]] (* _Harvey P. Dale_, Feb 10 2015 *)

%K nonn

%O 0,2

%A _R. H. Hardin_, Aug 14 2009

%E Offset changed, terms prepended accordingly, and b-file amended by _Harvey P. Dale_, Feb 11 2015