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,2

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

Table of n, a(n) for n=0..31.

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

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

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

Crossrefs

Cf. A007931, A062257, A062259.

Sequence in context: A062257 A208127 A172316 * A239560 A066178 A122189

Adjacent sequences: A062255 A062256 A062257 * A062259 A062260 A062261

Keyword

nonn

Author

Vladeta Jovovic, Jun 14 2001

Status

approved