A062257 Number of (0,1)-strings of length n with no occurrences of the substrings 10101101 and 1110101.

1, 2, 4, 8, 16, 32, 64, 127, 251, 496, 981, 1940, 3837, 7590, 15015, 29704, 58763, 116249, 229971, 454942, 899991, 1780410, 3522102, 6967611, 13783703, 27267665, 53942368, 106711708, 211102869, 417615105, 826148769, 1634332138

Offset: 0

Author

Vladeta Jovovic, Jun 14 2001

Keywords

• nonn

References

• I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (Example 2.8.11).

Crossrefs

Cf. A062258, A062259.

Formula

G.f.: (1+x^5+x^6+x^7-x^9)/(1+x^5-x^6-x^9-2*x-x^8+x^10). a(n) = 2*a(n-1)-a(n-5)+a(n-6)+a(n-8)+a(n-9)-a(n-10).