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

References

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

Links

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

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

Crossrefs

Cf. A062257, A062258.

Sequence in context: A006261 A290987 A145112 * A001949 A210031 A239558

Adjacent sequences: A062256 A062257 A062258 * A062260 A062261 A062262

Keyword

nonn

Author

Vladeta Jovovic, Jun 14 2001

Status

approved