

A108758


a(n) = 2*a(n1)  a(n4) + a(n5) 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, 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.: (1x)/(12*x+x^4x^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



