login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 0
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 (list; graph; refs; listen; history; text; internal format)
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, M. D. Weiner, n 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 20 14:03 EST 2020. Contains 332078 sequences. (Running on oeis4.)