%I #83 Nov 15 2021 09:55:27

%S 1,2,4,8,14,26,48,88,162,298,548,1008,1854,3410,6272,11536,21218,

%T 39026,71780,132024,242830,446634,821488,1510952,2779074,5111514,

%U 9401540,17292128,31805182,58498850,107596160,197900192,363995202,669491554,1231386948,2264873704

%N Number of ways to toss a coin n times and not get a run of four.

%H G. C. Greubel, <a href="/A135491/b135491.txt">Table of n, a(n) for n = 0..1000</a>

%H Elena Barcucci, Antonio Bernini, Stefano Bilotta, Renzo Pinzani, <a href="http://arxiv.org/abs/1601.07723">Non-overlapping matrices</a>, arXiv:1601.07723 [cs.DM], 2016. See column 2 of Table 2 p. 11.

%H Elena Barcucci, Antonio Bernini, Stefano Bilotta and Renzo Pinzani, <a href="https://doi.org/10.1016/j.tcs.2016.05.009">Non-overlapping matrices</a>, Theoretical Computer Science, Vol. 658, Part A (2017), 36-45.

%H B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, <a href="http://arxiv.org/abs/1212.6102">On Curling Numbers of Integer Sequences</a>, arXiv:1212.6102 [math.CO], 2012-2013.

%H B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Sloane/sloane3.html">On Curling Numbers of Integer Sequences</a>, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.

%H Emrah Kılıç, Talha Arıkan, <a href="https://doi.org/10.2298/FIL1715945K">Evaluation of Hessenberg determinants with recursive entries: generating function approach</a>, Filomat (2017) Vol. 31, Issue 15, pp. 4945-4962.

%H A. V. Zharkova, <a href="https://cyberleninka.ru/article/n/nedostizhimye-sostoyaniya-v-dinamicheskih-sistemah-assotsiirovannyh-s-tsepyami-i-tsiklami">Inaccesible States in Dynamic Systems Associated with Paths and Cycles</a>, Izv. Saratov Univ. (N.S.), Ser. Math. Mech. Inform., 11 (2011), 116-122.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1, 1, 1).

%F a(n) = 2*A000073(n+2) for n > 0.

%F a(n) = a(n-1) + a(n-2) + a(n-3) for n > 3.

%F G.f.: -(x+1)*(x^2+1)/(x^3+x^2+x-1).

%F a(n) = nearest integer to b*c^n, where b = 1.2368... and c = 1.839286755... is the real root of x^3-x^2-x-1 = 0. See A058265. - _N. J. A. Sloane_, Jan 06 2010

%F G.f.: (1-x^4)/(1-2*x+x^4) and generally to "not get a run of k" (1-x^k)/(1-2*x+x^k). - _Geoffrey Critzer_, Feb 01 2012

%F G.f.: Q(0)/x^2 - 2/x- 1/x^2, where Q(k) = 1 + (1+x)*x^2 + (2*k+3)*x - x*(2*k+1 +x+x^2)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Oct 04 2013

%F a(n) = A000213(n+3) - A000213(n+2), n>=1. - _Peter M. Chema_, Jan 11 2017.

%t LinearRecurrence[{1, 1, 1}, {1, 2, 4, 8}, 36] (* _Vladimir Joseph Stephan Orlovsky_, Jul 23 2011; first term 1 added by _Georg Fischer_, Apr 02 2019 *)

%o (PARI) Vec(1-2*x*(1+x+x^2)/(-1+x+x^2+x^3) + O(x^100)) \\ _Altug Alkan_, Dec 10 2015

%Y Cf. A000073. Column 2 of A265624. Cf. A135492, A135493, A000213, A058265.

%K nonn,easy

%O 0,2

%A James R FitzSimons (cherry(AT)getnet.net), Feb 07 2008

%E More terms from _Robert G. Wilson v_, Feb 10 2008

%E a(0)=1 prepended by _Alois P. Heinz_, Dec 10 2015