A198442 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,0).

0, 0, 2, 3, 6, 8, 12, 15, 20, 24, 30, 35, 42, 48, 56, 63, 72, 80, 90, 99, 110, 120, 132, 143, 156, 168, 182, 195, 210, 224, 240, 255, 272, 288, 306, 323, 342, 360, 380, 399, 420, 440, 462, 483, 506, 528, 552, 575, 600, 624, 650, 675, 702, 728, 756, 783, 812

Offset: 1

Author

Paul Weisenhorn, Oct 25 2011

Keywords

• nonn
• easy

Comments

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

Abel(n) = A002620(n-1) = (2*n*(n - 2) + 1 - (-1)^n)/8.

Kain(n) = A004526(n-1) = floor((n - 1)/2).

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) = 16/3.

Essentially the same as A035106. - R. J. Mathar, Oct 27 2011

The sequence 2*a(n) is denoted as chi(n) by McKee (1994) and is the degree of the division polynomial f_n as a polynomial in x. He notes that "If x is given weight 1, a is given weight 2, and b is given weight 3, then all the terms in f_n(a, b, x) have weight chi(n)". - Michael Somos, Jan 09 2015

In Duistermaat (2010), at the end of section 11.2 The Elliptic Billiard, on page 492 the number of k-periodic fibers counted with multiplicities of the QRT root is given by equation (11.2.8) as "1/4 k^2 + 3{k/2}(1 - {k/2}) - 1 = n^2 - 1 when k = 2n, n^2 + n when k = 2n+1, for every integer k." - Michael Somos, Mar 14 2023

Examples

			For n = 6 the a(6) = 8 solutions are (0,0,0,1,1,0), (0,1,0,1,1,0),(0,0,1,1,1,0), (1,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,0), (0,1,0,1,0,0) for Kain.
G.f. = 2*x^3 + 3*x^4 + 6*x^5 + 8*x^6 + 12*x^7 + 15*x^8 + 20*x^9 + ...
		

References

• J. J. Duistermaat, Discrete Integrable Systems, 2010, Springer Science+Business Media.
• A. Engel, Wahrscheinlichkeitsrechnung und Statistik, Band 2, Klett, 1978, pages 25-26.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..10000
• J. McKee, Computing division polynomials, Math. Comp. 63 (1994), 767-771. MR1248973 (95a:11110)
• Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

Crossrefs

Cf. A000004, A002620, A004526, A004652, A005843, A008585, A008586, A023443, A028242, A047221, A047336, A052928, A242477, A265611.

Cf. A035106, A079524, A238377.

Programs

Magma

[(2*n^2-5-3*(-1)^n)/8: n in [1..60]]; // Vincenzo Librandi, Oct 28 2011

Maple

for n from 1 by 2 to 99 do
  a(n):=(n^2-1)/4:
  a(n+1):=(n+1)^2/4-1:
end do:
seq(a(n),n=1..100);

Mathematica

a[ n_] := Quotient[ n^2 - 1, 4]; (* Michael Somos, Jan 09 2015 *)

PARI

a(n)=([1,1,0,0,0,0;0,0,1,1,0,0;0,1,0,0,1,0;0,0,0,1,1,0;0,0,0,0,0,2;0,0,0,0,0,2]^n)[1,5] \\ Charles R Greathouse IV, Oct 26 2011

PARI

{a(n) = (n^2 - 1) \ 4}; /* Michael Somos, Jan 09 2015 */

Perl

sub a {
    my ($t, $n) = (0, shift);
    for (0..((1<<$n)-1)) {
        my $str = substr unpack("B32", pack("N", $_)), -$n;
        $t++ if ($str =~ /1.0$/ and not $str =~ /1.0./);
    }
    return $t
} # Charles R Greathouse IV, Oct 26 2011

Sage

def A198442():
    yield 0
    x, y = 0, 2
    while True:
       yield x
       x, y = x + y, x//y + 1
a = A198442(); print([next(a) for i in range(57)]) # Peter Luschny, Dec 22 2015

Formula

a(n) = (2*n^2 - 5 - 3*(-1)^n)/8.

a(2*n) = n^2 - 1; a(2*n+1) = n*(n + 1).

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

G.f.: x^3*(2 - x)/((1 + x)*(1 - x)^3). - R. J. Mathar, Oct 27 2011

a(n) = a(-n) for all n in Z. a(0) = -1. - Michael Somos, Jan 09 2015

0 = a(n)*(+a(n+1) - a(n+2)) + a(n+1)*(-1 - a(n+1) + a(n+2)) for all n in Z. - Michael Somos, Jan 09 2015

1 = a(n) - a(n+1) - a(n+2) + a(n+3), 2 = a(n) - 2*a(n+2) + a(n+4) for all n in Z. - Michael Somos, Jan 09 2015

a(n) = A002620(n+2) - A052928(n+2) for n >= 1. (Note A265611(n) = A002620(n+1) + A052928(n+1) for n >= 1.) - Peter Luschny, Dec 22 2015

a(n+1) = A110654(n)^2 + A110654(n)*(2 - (n mod 2)), n >= 0. - Fred Daniel Kline, Jun 08 2016

a(n) = A004526(n)*A004526(n+3). - Fred Daniel Kline, Aug 04 2016

a(n) = floor((n^2 - 1)/4). - Bruno Berselli, Mar 15 2021

Extensions

a(12) inserted by Charles R Greathouse IV, Oct 26 2011