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

1, 2, 4, 8, 14, 26, 48, 88, 162, 298, 548, 1008, 1854, 3410, 6272, 11536, 21218, 39026, 71780, 132024, 242830, 446634, 821488, 1510952, 2779074, 5111514, 9401540, 17292128, 31805182, 58498850, 107596160, 197900192, 363995202, 669491554, 1231386948, 2264873704

Offset

0,2

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Elena Barcucci, Antonio Bernini, Stefano Bilotta, Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016. See column 2 of Table 2 p. 11.

Elena Barcucci, Antonio Bernini, Stefano Bilotta and Renzo Pinzani, Non-overlapping matrices, Theoretical Computer Science, Vol. 658, Part A (2017), 36-45.

B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], 2012-2013.

B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.

Emrah Kılıç, Talha Arıkan, Evaluation of Hessenberg determinants with recursive entries: generating function approach, Filomat (2017) Vol. 31, Issue 15, pp. 4945-4962.

A. V. Zharkova, Inaccesible States in Dynamic Systems Associated with Paths and Cycles, Izv. Saratov Univ. (N.S.), Ser. Math. Mech. Inform., 11 (2011), 116-122.

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

Formula

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

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

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

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

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

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

a(n) = A000213(n+3) - A000213(n+2), n>=1. - Peter M. Chema, Jan 11 2017.

Mathematica

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

Prog

(PARI) Vec(1-2*x*(1+x+x^2)/(-1+x+x^2+x^3) + O(x^100)) \\ Altug Alkan, Dec 10 2015

Crossrefs

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

Sequence in context: A117633 A308148 A273154 * A164154 A164156 A257934

Adjacent sequences: A135488 A135489 A135490 * A135492 A135493 A135494

Keyword

nonn,easy

Author

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

Extensions

More terms from Robert G. Wilson v, Feb 10 2008

a(0)=1 prepended by Alois P. Heinz, Dec 10 2015

Status

approved