A135493 Number of ways to toss a coin n times and not get a run of six.

1, 2, 4, 8, 16, 32, 62, 122, 240, 472, 928, 1824, 3586, 7050, 13860, 27248, 53568, 105312, 207038, 407026, 800192, 1573136, 3092704, 6080096, 11953154, 23499282, 46198372, 90823608, 178554512, 351028928, 690104702, 1356710122, 2667221872

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,1).

Formula

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

From R. J. Mathar, Feb 10 2008: (Start)

O.g.f.: -1 - 2/(-1+x+x^2+x^3+x^4+x^5).

a(n) = 2*A001591(n+4) for n>=1. (End)

Mathematica

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

Prog

(PARI) a(n)=if(n, ([0, 1, 0, 0, 0; 0, 0, 1, 0, 0; 0, 0, 0, 1, 0; 0, 0, 0, 0, 1; 1, 1, 1, 1, 1]^(n-1)*[2; 4; 8; 16; 32])[1, 1], 1) \\ Charles R Greathouse IV, May 20 2026

Crossrefs

Cf. A135491, A135492.

Sequence in context: A355520 A274005 A027560 * A216241 A283837 A111663

Adjacent sequences: A135490 A135491 A135492 * A135494 A135495 A135496

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, May 22 2025

Status

approved