[seqfan] Re: game series

[Robert Israel]

On Fri, 28 Jan 2011, Peter Pein wrote:

> On 28.01.2011 10:10, Dmitry Kamenetsky wrote:
>> Hello Sequence Fans,
>> 
>> Recently I have been looking at the following problem. There is a series of
>> n games played between two teams. The outcome of each game is either a win
>> or a loss (no draws).
>> A team wins the whole series if it wins k=floor(n/2)+1 games or more. Now 
>> if
>> a team reaches the magic number of k wins then the games that follow (if
>> there are any) are
>> dead games, because their outcome cannot affect the outcome of the series.
>> So a natural question arises: out of all the possible 2^n series how many 
>> of
>> them will have
>> at least one dead game? This forms the sequence 
>> 0,0,4,4,20,24,88,116,372,...
>> This sequence is not in the OEIS and neither is its version for all odd n.
> Hi Dimitry,
>
> what did I do wrong while trying to reconstruct the sequence 
> {0,0,4,4,20,24,88..} ?
>
> I tried to find those sequences of wins/losses which contain a sequence of 
> wins/losses of length >= Floor[n/2]+1 followed by at least one "dead" game:
>
> In[1]:= 
> f[n_]:=Count[Tuples[{0,1},{n}],({___,0,s:1..,0,__}|{___,1,s:0..,1,__})/;Length[{s}]>=Floor[n/2]+1]
> In[3]:= f/@Range[20]
> Out[3]= {0,0,0,0,0,0,4,4,20,20,68,68,196,196,516,516,1284,1284,3076,3076}
>
> Did I misunderstand your definition? Please enlighten me!
>
> Cheers,
>  Peter

The last game is "alive" if and only if the result of the first n-1 games
is either
(if n is odd) (n-1)/2 wins for both teams, or
(if n is even) n/2 wins for one and n/2-1 for the other.
So if n is odd the number of series with at least one dead game is
2^n - 2 (n-1 choose (n-1)/2)
and if n is even it is 2^n - 4 (n-1 choose n/2).
This gives me 
0, 0, 4, 4, 20, 24, 88, 116, 372, 520, 1544, 2248, 6344, 9520, 25904, ...
agreeing with Dmitry.

Robert Israel                                israel at math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            Vancouver, BC, Canada