A118891 Number of binary sequences of length n with no subsequence 01110.

1, 2, 4, 8, 16, 31, 60, 116, 223, 428, 820, 1569, 3002, 5744, 10992, 21039, 40273, 77095, 147588, 282538, 540881, 1035440, 1982194, 3794602, 7264164, 13906079, 26620957, 50961552, 97557726, 186758657, 357519595, 684414146, 1310201570

Offset

0,2

Comments

This is a_4(n) in the Doroslovacki reference.

Links

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

R. Doroslovacki, Binary sequences without 011...110 (k-1 1's) for fixed k, Mat. Vesnik 46 (1994), no. 3-4, 93-98.

Formula

Empirical g.f.: -(x^8+x^7-x^5+2*x^4-x+1) / (x^9-x^7-x^6+4*x^5-2*x^4-2*x^2+3*x-1). - Colin Barker, Aug 11 2013

Prog

(PARI) { a4(n) = 1 + sum(i=1, n, sum(j=0, n-i, sum(k=0, (n-i-j)\2, sum(l=0, (n-i-j-2*k)\4, binomial(i-1, j)*binomial(i-1-j, k)*binomial(i-1-j-2*k, l)*binomial(n-i-j-2*k-3*l+1, l+1))))) }

Crossrefs

Cf. A000045, A005251, A049864.

Sequence in context: A189075 A345372 A189077 * A107066 A141019 A210003

Adjacent sequences: A118888 A118889 A118890 * A118892 A118893 A118894

Keyword

nonn

Author

Max Alekseyev, Jun 26 2007

Extensions

More terms from Max Alekseyev, Sep 25 2009

Status

approved