A049864 a(n) = Sum_{k=0,1,2,...,n-4,n-2,n-1} a(k); a(n-3) is not a summand; 3 initial terms required.

1, 1, 1, 2, 4, 8, 15, 28, 52, 97, 181, 338, 631, 1178, 2199, 4105, 7663, 14305, 26704, 49850, 93058, 173717, 324288, 605368, 1130077, 2109583, 3938086, 7351463, 13723420, 25618337, 47823297, 89274637, 166654357, 311103754, 580756168, 1084132616

Offset

0,4

Comments

Number of binary sequences of length n-2 with no subsequence 0110. E.g., a(7)=28 because among the 32 (=2^5) binary sequences of length 5 only 01100,01101,00110 and 10110 contain the subsequence 0110. - Emeric Deutsch, May 04 2006

This is a_3(n) in the Doroslovacki reference. - Max Alekseyev, Jun 26 2007

Column 0 of A118890. - Emeric Deutsch, May 04 2006

Links

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

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

Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1).

Formula

a(n) = 2*a(n-1) - a(n-3) + a(n-4); 4 initial terms required.

G.f.: (1+z)*(1-z)^2/(1 - 2z + z^3 - z^4). - Emeric Deutsch, May 04 2006

Maple

(With a different offset:) a[0]:=1:a[1]:=2:a[2]:=4:a[3]:=8: for n from 4 to 35 do a[n]:=2*a[n-1]-a[n-3]+a[n-4] od: seq(a[n], n=0..35); # Emeric Deutsch, May 04 2006

Mathematica

LinearRecurrence[{2, 0, -1, 1}, {1, 1, 1, 2}, 40] (* Harvey P. Dale, Sep 24 2013 *)

Crossrefs

Cf. A005251, A049858, A118890, A118891, A118892.

Sequence in context: A008937 A128805 A141018 * A239554 A268393 A118870

Adjacent sequences: A049861 A049862 A049863 * A049865 A049866 A049867

Keyword

nonn

Author

Clark Kimberling

Extensions

Edited by N. J. A. Sloane, Nov 16 2007, at the suggestion of Max Alekseyev

Status

approved