A062258 Number of (0,1)-strings of length n not containing the substring 0100100.

1, 2, 4, 8, 16, 32, 64, 127, 252, 500, 993, 1972, 3916, 7776, 15441, 30662, 60887, 120906, 240088, 476753, 946709, 1879921, 3733040, 7412858, 14720031, 29230199, 58043664, 115259801, 228876346, 454489608, 902499570, 1792132228

Offset: 0

Author

Vladeta Jovovic, Jun 14 2001

Keywords

• nonn

Comments

Also, number of (0,1)-strings of length n not containing the substring 1001001. - N. J. A. Sloane, Apr 02 2012

References

• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (Problem 2.8.2).
• 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]

Links

• Index entries for linear recurrences with constant coefficients, signature (2,0,-1,2,0,-1,1).

Crossrefs

Cf. A007931, A062257, A062259.

Programs

Mathematica

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 *)

Formula

G.f.: (1 + x^3 + x^6)/(1 - 2*x + x^3 - 2*x^4 + x^6 - x^7).

a(n) = 2*a(n-1) - a(n-3) + 2*a(n-4) - a(n-6) + a(n-7).