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

Author

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

Keywords

• nonn

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

Crossrefs

Cf. A135491, A135492.

Programs

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

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)

Extensions

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

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