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

%I #16 Oct 17 2016 00:50:53

%S 2,4,8,16,30,58,112,216,416,802,1546,2980,5744,11072,21342,41138,

%T 79296,152848,294624,567906,1094674,2110052,4067256,7839888,15111870,

%U 29129066,56148080,108228904,208617920,402123970,775118874,1494089668,2879950432

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

%H G. C. Greubel, <a href="/A135492/b135492.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,1).

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

%F a(n) = 2*A000078(n+3).

%F G.f.: -2*x*(x+1)*(1+x^2)/(x^4+x^3+x^2+x-1). - _Colin Barker_, Jun 12 2012

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

%t LinearRecurrence[{1, 1, 1, 1}, {2, 4, 8, 16}, 25] (* _G. C. Greubel_, Oct 15 2016 *)

%o (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

%Y Cf. A135491, A135493.

%K nonn,easy

%O 1,1

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

%E Corrected and extended by _Robert G. Wilson v_, Feb 10 2008