login
Number of binary strings of length n with no substrings equal to 0010 or 0101.
1

%I #17 Feb 14 2018 21:09:51

%S 1,2,4,8,14,25,45,81,146,264,477,861,1554,2805,5063,9139,16497,29779,

%T 53754,97031,175150,316162,570702,1030171,1859556,3356674,6059113,

%U 10937270,19742803,35637620,64329263,116120383,209608236,378362622,682980194,1232843622

%N Number of binary strings of length n with no substrings equal to 0010 or 0101.

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

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

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

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

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

%o (PARI) Vec((1 + x^2 + x^3 + x^5)/(1 - 2*x + x^2 - x^3 - x^6) + 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