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

Author

Max Alekseyev, Jun 26 2007

Keywords

• nonn

Comments

This is a_4(n) in the Doroslovacki reference.

Links

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

Crossrefs

Cf. A000045, A005251, A049864.

Programs

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

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

Extensions

More terms from Max Alekseyev, Sep 25 2009