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

Author

Paul Weisenhorn, Oct 28 2011

Keywords

• nonn
• easy

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.

Examples

			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.
		

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

Crossrefs

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

Programs

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

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

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