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

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

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy

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

• 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).

Crossrefs

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

Programs

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

Formula

a(n) = 2*a(n-1) - a(n-3) + a(n-4).

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

Extensions

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