A164394 - OEIS

%I #20 Feb 15 2018 11:56:08

%S 1,2,4,8,14,24,42,74,130,228,400,702,1232,2162,3794,6658,11684,20504,

%T 35982,63144,110810,194458,341250,598852,1050912,1844222,3236384,

%U 5679458,9966754,17490434,30693572,53863464,94523790,165877688,291095050,510836202

%N Number of binary strings of length n with no substrings equal to 0001 or 0100.

%H R. H. Hardin, <a href="/A164394/b164394.txt">Table of n, a(n) for n = 0..500</a>

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

%F a(n) = 2*a(n-1) - a(n-2) + a(n-3) for n > 3. - _Andrew Howroyd_, Feb 14 2018

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

%F a(n) = 2*A005251(n + 2) for n > 0. - _Andrew Howroyd_, Feb 14 2018

%p a:= n-> (<<0|1|0>, <0|0|1>, <1|-1|2>>^n. <<2,2,4>>)[1,1]-0^n:

%p seq(a(n), n=0..40);  # _Alois P. Heinz_, Feb 14 2018

%t LinearRecurrence[{2,-1,1}, {1, 2, 4, 8}, 50] (* _G. C. Greubel_, Sep 18 2017 *)

%o (PARI) Vec((1 + x^2 + x^3)/(1 - 2*x + x^2 - x^3) + O(x^40)) \\ _G. C. Greubel_, Sep 18 2017

%K nonn

%O 0,2

%A _R. H. Hardin_, Aug 14 2009

%E a(0)-a(3) prepended by _Andrew Howroyd_, Feb 14 2018