login
Number of binary sequences of length n with no subsequence 01110.
2

%I #7 Aug 11 2013 14:12:45

%S 1,2,4,8,16,31,60,116,223,428,820,1569,3002,5744,10992,21039,40273,

%T 77095,147588,282538,540881,1035440,1982194,3794602,7264164,13906079,

%U 26620957,50961552,97557726,186758657,357519595,684414146,1310201570

%N Number of binary sequences of length n with no subsequence 01110.

%C This is a_4(n) in the Doroslovacki reference.

%H R. Doroslovacki, <a href="http://www.emis.de/journals/MV/9434/mv943407.ps">Binary sequences without 011...110 (k-1 1's) for fixed k</a>, Mat. Vesnik 46 (1994), no. 3-4, 93-98.

%F 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

%o (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))))) }

%Y Cf. A000045, A005251, A049864.

%K nonn

%O 0,2

%A Max Alekseyev, Jun 26 2007

%E More terms from _Max Alekseyev_, Sep 25 2009