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

0, 0, 0, 2, 3, 5, 10, 18, 31, 56, 100, 177, 315, 561, 997, 1773, 3154, 5609, 9975, 17741, 31552, 56114, 99798, 177489, 315660, 561395, 998430, 1775687, 3158023, 5616480, 9988795, 17764868, 31594456, 56190096, 99932940, 177728697, 316086865, 562154046

Offset

1,4

Comments

If the sequence ends with (0,0,1,1) Abel wins.

If the sequence ends with (1,1,1,1) Kain wins.

Abel(n)=A199925(n); Kain(n)=A199926(n).

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

Win probability of Kain = sum(Kain(n)/2^n)=1/4.

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

References

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

Links

Table of n, a(n) for n=1..38.

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

Formula

a(n) = a(n-1)+a(n-2)+a(n-3)-a(n-5) for n>7.

a(n) = 2*a(n-1)-a(n-4)-a(n-5)+a(n-6) for n>8.

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

Example

For n=5 the a(5)=3 solutions are (0,0,0,1,1),(1,0,0,1,1) for Abel, (0,1,1,1,1) for Kain.

Maple

a(1):=0: a(2):=0: a(3):=0: a(4):=2; a(5):=3:
a(6):=5: a(7):=10: pot:=2^3: ml:=0:
for n from 4 to 7 do
  pot:=2*pot:
  ml:=ml+n*a(n)/pot:
end do:
for n from 8 to 100 do
  pot:=2*pot:
  a(n):=a(n-1)+a(n-2)+a(n-3)-a(n-5):
  ml:=ml+n*a(n)/pot:
end do:
printf("10.5f", ml):
seq(a(n), n=0..100);

Crossrefs

Cf. A199925, A199926.

Sequence in context: A339293 A195507 A117222 * A081172 A318301 A030032

Adjacent sequences: A199591 A199592 A199593 * A199595 A199596 A199597

Keyword

nonn,easy

Author

Paul Weisenhorn, Nov 12 2011

Status

approved