Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #16 Jan 24 2022 07:11:18
%S 1,2,4,8,16,32,64,127,252,500,993,1972,3916,7776,15441,30662,60887,
%T 120906,240088,476753,946709,1879921,3733040,7412858,14720031,
%U 29230199,58043664,115259801,228876346,454489608,902499570,1792132228
%N Number of (0,1)-strings of length n not containing the substring 0100100.
%C Also, number of (0,1)-strings of length n not containing the substring 1001001. - _N. J. A. Sloane_, Apr 02 2012
%D I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (Problem 2.8.2).
%D Reilly, J. W.; Stanton, R. G. Variable strings with a fixed substring. Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971), pp. 483--494. Louisiana State Univ., Baton Rouge, La.,1971. MR0319775 (47 #8317) [From _N. J. A. Sloane_, Apr 02 2012]
%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1,2,0,-1,1).
%F G.f.: (1 + x^3 + x^6)/(1 - 2*x + x^3 - 2*x^4 + x^6 - x^7).
%F a(n) = 2*a(n-1) - a(n-3) + 2*a(n-4) - a(n-6) + a(n-7).
%t CoefficientList[Series[(1+x^3+x^6)/(1-2x+x^3-2x^4+x^6-x^7),{x,0,40}],x] (* or *) LinearRecurrence[{2,0,-1,2,0,-1,1},{1,2,4,8,16,32,64},40] (* _Harvey P. Dale_, Aug 10 2021 *)
%Y Cf. A007931, A062257, A062259.
%K nonn
%O 0,2
%A _Vladeta Jovovic_, Jun 14 2001