A062259 Number of (0,1)-strings of length n that avoid the substrings of substrings 11101011 and 101111.

1, 2, 4, 8, 16, 32, 63, 124, 243, 476, 933, 1830, 3590, 7043, 13818, 27110, 53186, 104342, 204701, 401588, 787846, 1545619, 3032243, 5948749, 11670441, 22895434, 44916973, 88119508, 172875575, 339152648, 665360153, 1305324126, 2560825244

Offset: 0

Author

Vladeta Jovovic, Jun 14 2001

Keywords

• nonn

References

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

Crossrefs

Cf. A062257, A062258.

Formula

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

Goulden and Jackson give the g.f. in the equivalent form (1+x^5+x^6-x^8-x^9-x^10)/(1-2*x+x^5-2*x^7+x^9+x^11). - N. J. A. Sloane, Apr 09 2011