login
Number of sequences of n coin flips, that win on the last flip, if the sequence of flips ends with (1,1,0) or (1,0,1).
1

%I #30 Feb 10 2020 01:21:05

%S 0,0,2,3,4,7,11,16,24,36,53,78,115,169,248,364,534,783,1148,1683,2467,

%T 3616,5300,7768,11385,16686,24455,35841,52528,76984,112826,165355,

%U 242340,355167,520523,762864,1118032,1638556,2401421,3519454,5158011

%N Number of sequences of n coin flips, that win on the last flip, if the sequence of flips ends with (1,1,0) or (1,0,1).

%C If the sequence ends with (1,1,0) Abel wins; if it ends with (1,0,1) Kain wins.

%C Abel(n)=A077868(n-3); Kain(n)=A000930(n-3).

%C Win probability for Abel=sum(Abel(n)/2^n)= 2/3.

%C Win probability for Kain=sum(Kain(n)/2^n)= 1/3.

%C Mean length of the game=sum(n*a(n)/2^n)= 6.

%D A. Engel, Wahrscheinlichkeit und Statistik, Band 2, Klett, 1978, pages 25-26.

%H G. C. Greubel, <a href="/A196382/b196382.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 (2,-1,1,-1).

%F a(n) = +2*a(n-1) -a(n-2) +a(n-3) -a(n-4), n>=5.

%F G.f.: x^3*(2-x)/((1-x)*(1-x-x^3)).

%F a(n) = 2*A077868(n-3) - A077868(n-4). - _R. J. Mathar_, Jan 11 2017

%F a(n) = a(n-1) + a(n-3) + 1, n>3. - _Greg Dresden_, Feb 09 2020

%e For n=6 the a(6)=7 solutions are (0,0,0,1,1,0),(1,0,0,1,1,0),(0,0,1,1,1,0),(0,1,1,1,1,0),(1,1,1,1,1,0) for Abel and (0,0,0,1,0,1),(1,0,0,1,0,1) for Kain.

%p a(1):=0: a(2):=0: a(3):=2: a(4):=3: a(5):=4:

%p for n from 6 to 100 do

%p a(n):=a(n-1)+a(n-2)-a(n-5):

%p end do:

%p seq(a(n),n=1..100);

%t Rest[CoefficientList[Series[x^3*(2 - x)/((1 - x)*(1 - x - x^3)), {x,0,50}], x]] (* _G. C. Greubel_, May 02 2017 *)

%o (PARI) x='x+O('x^50); concat([0,0], Vec(x^3*(2 - x)/((1 - x)*(1 - x - x^3)))) \\ _G. C. Greubel_, May 02 2017

%Y Cf. A000930, A077868, A179070 (first differences).

%K nonn,easy

%O 1,3

%A _Paul Weisenhorn_, Oct 28 2011