A108758 a(n) = 2*a(n-1) - a(n-4) + a(n-5) with a(-1)=a(0)=a(1)=1, a(2)=2, a(3)=4, a(4)=7.

1, 1, 1, 2, 4, 7, 14, 27, 52, 101, 195, 377, 729, 1409, 2724, 5266, 10180, 19680, 38045, 73548, 142182, 274864, 531363, 1027223, 1985812, 3838942, 7421385, 14346910, 27735231, 53617332, 103652221, 200378917, 387369513, 748856925, 1447678961

Offset

-1,4

Comments

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

Links

Table of n, a(n) for n=-1..33.

D. Birmajer, J. B. Gil, and M. 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).

Formula

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

Example

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

Mathematica

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

Crossrefs

Sequence in context: A079968 A280194 A001631 * A018085 A167751 A190822

Adjacent sequences: A108755 A108756 A108757 * A108759 A108760 A108761

Keyword

nonn,easy

Author

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

Extensions

Edited by Robert G. Wilson v, Jun 25 2005

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

Status

approved