-1,4

An unbiased coin is tossed n times and the resulting sequence of heads and tails is written linearly. Number of strings out of 2^n possible strings, having no three consecutive heads (HHH's) is given by the above sequence (with suitable offset).

Starting (1, 1, 2, 4, 7, ...) = INVERT transform of (1, 1, 0, 1, 1, 1, 1, ...). - Gary W. Adamson, Apr 27 2009

a(n) is the number of compositions of n avoiding the part 4. - Joerg Arndt, Jul 13 2014

Michael De Vlieger, Table of n, a(n) for n = -1..3494

Félix Balado and Guénolé C. M. Silvestre, Systematic Enumeration of Fundamental Quantities Involving Runs in Binary Strings, arXiv:2602.10005 [math.CO], 2026. See p. 15.

Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, example 11.

Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3

James J. Madden, A Generating Function for the Distribution of Runs in Binary Words, arXiv:1707.04351 [math.CO], 2017. Theorem 1.1, r=4, k=0.

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

G.f.: (1-x)/(1-2*x+x^4-x^5) + 1/x. - Vladimir Kruchinin, May 11 2011

a(5)=14 counts all 2^4 = 16 sequences on {H,T} except HHHT and THHH. We note that coin flip sequences with more than 3 consecutive H's are included in this count. In particular a(5)=14 includes HHHH. Cf. A049856 (comment by Alois P. Heinz) where sequences having no H runs of length 2 are counted. - Geoffrey Critzer, Jan 22 2014

Table[SeriesCoefficient[Series[(1 - x - x^2 + x^4 - x^5)/(1 - 2*x + x^4 - x^5), {x, 0, 34}], n], {n, 0, 34}] (* L. Edson Jeffery, Aug 02 2014 *)

LinearRecurrence[{2, 0, 0, -1, 1}, {1, 1, 1, 2, 4, 7}, 40] (* Harvey P. Dale, Mar 21 2018 *)

Sequence in context: A079968 A280194 A001631 * A018085 A167751 A190822

Adjacent sequences: A108755 A108756 A108757 * A108759 A108760 A108761

nonn,easy

Mrs. J. P. Shiwalkar (jyotishiwalkar(AT)rediffmail.com) and M. N. Deshpande (dpratap_ngp(AT)sancharnet.in), Jun 24 2005

Edited by Robert G. Wilson v, Jun 25 2005

Edited and changed offset to -1 to better match comments. - Joerg Arndt, Aug 12 2014

approved