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
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).
Programs
-
Mathematica
a[n_] := a[n] = a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4]; a[1] = 2; a[2] = 4; a[3] = 8; a[4] = 16; Array[a, 33] (* Robert G. Wilson v, Feb 10 2008 *) LinearRecurrence[{1, 1, 1, 1}, {2, 4, 8, 16}, 25] (* G. C. Greubel, Oct 15 2016 *)
-
PARI
a(n)=([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
Formula
a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4).
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
Extensions
Corrected and extended by Robert G. Wilson v, Feb 10 2008
a(0)=1 prepended by Alois P. Heinz, May 22 2025