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

0, 0, 2, 3, 4, 7, 11, 16, 24, 36, 53, 78, 115, 169, 248, 364, 534, 783, 1148, 1683, 2467, 3616, 5300, 7768, 11385, 16686, 24455, 35841, 52528, 76984, 112826, 165355, 242340, 355167, 520523, 762864, 1118032, 1638556, 2401421, 3519454, 5158011

Offset

1,3

Comments

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

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

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

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

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

References

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

Links

G. C. Greubel, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (2,-1,1,-1).

Formula

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

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

a(n) = 2*A077868(n-3) - A077868(n-4). - R. J. Mathar, Jan 11 2017

a(n) = a(n-1) + a(n-3) + 1, n>3. - Greg Dresden, Feb 09 2020

Example

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.

Maple

a(1):=0: a(2):=0: a(3):=2: a(4):=3: a(5):=4:
for n from 6 to 100 do
  a(n):=a(n-1)+a(n-2)-a(n-5):
end do:
seq(a(n), n=1..100);

Mathematica

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

Prog

(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

Crossrefs

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

Sequence in context: A125621 A141001 A333260 * A120415 A023361 A210518

Adjacent sequences: A196379 A196380 A196381 * A196383 A196384 A196385

Keyword

nonn,easy

Author

Paul Weisenhorn, Oct 28 2011

Status

approved