A135492 Number of ways to toss a coin n times and not get a run of five.

1, 2, 4, 8, 16, 30, 58, 112, 216, 416, 802, 1546, 2980, 5744, 11072, 21342, 41138, 79296, 152848, 294624, 567906, 1094674, 2110052, 4067256, 7839888, 15111870, 29129066, 56148080, 108228904, 208617920, 402123970, 775118874, 1494089668, 2879950432

Offset

0,2

Links

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

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

Formula

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

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

G.f.: 1-2*x*(x+1)*(1+x^2)/(x^4+x^3+x^2+x-1). - Colin Barker, Jun 12 2012

G.f.: (1-x^5)/(1-2*x+x^5). - after Geoffrey Critzer's general "no run of k" form, see A135491.

Mathematica

a[n_] := a[n] = a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4]; a[0] = 1; a[1] = 2; a[2] = 4; a[3] = 8; a[4] = 16; Array[a, 33, 0] (* Robert G. Wilson v, Feb 10 2008 *)
(* Alternative: *)
LinearRecurrence[{1, 1, 1, 1}, {1, 2, 4, 8, 16}, 25] (* G. C. Greubel, Oct 15 2016 *)

Prog

(PARI) a(n)=if(n<1, 1, ([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; 1, 1, 1, 1]^(n-1)*[2; 4; 8; 16])[1, 1]) \\ Charles R Greathouse IV, Oct 17 2016

Crossrefs

Cf. A135491, A135493.

Sequence in context: A344614 A337664 A378197 * A164191 A164193 A164192

Adjacent sequences: A135489 A135490 A135491 * A135493 A135494 A135495

Keyword

nonn,easy

Author

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

Extensions

Corrected and extended by Robert G. Wilson v, Feb 10 2008

a(0)=1 prepended by Alois P. Heinz, May 22 2025

Status

approved