Theory of 'Runs'

Date: 8/20/96 at 20:3:2
From: Anonymous
Subject: The Theory of Runs

Suppose that 7 boys and 13 girls line up in a row. Let S be the number 
of places in the row where a boy and a girl are standing next to each 
other. For example, for the row GBBGGGBGBGGGBGBGGBGG we have S = 12.  
If all possible orders of these 20 people are considered, what is the 
average value of S? Can you generalize this result to a group of m 
boys and n girls?

Thanks,
Michael

Date: 8/22/96 at 18:5:54
From: Doctor Anthony
Subject: Re: The Theory of Runs

This problem is an example on the theory of 'runs'. If we have an 
ordered sequence of elements of two kinds, then a sequence of elements 
of like kind is called a 'run'. Thus the sequence aaabaabbba starts 
with an 'a' run of length 3; it is followed by runs of length 1, 2, 3, 
1, respectively. The 'a' and 'b' runs alternate so that the total 
number of runs is always one plus the number of unlike neighbours in 
the sequence. Here the number of runs is 5, and the number of unlike 
neighbours is 4.

The number of distinguishable arrangements in runs is closely 
associated with occupancy problems in which r balls are placed at 
random into n cells.

We represent the balls by stars '*' and the cells by bars | |. Thus
|***|*| | | |****| is used as a symbol for the distribution of r=8 
balls into n=6 cells with occupancy numbers 3, 1, 0, 0, 0, 4. Such a 
symbol necessarily starts and ends with a bar, but the remaining n-1 
bars and r stars can appear in any order. It is clear therefore that 
the number of distinguishable arrangements is:

     (n+r-1)_C_(r)    or   (n+r-1)_C_(n-1)

If we specify that no cell should be empty, this imposes the 
restriction that no two bars be adjacent. The r stars leave r-1 spaces 
of which n-1 are to be occupied by bars, and this can be done in 
(r-1)_C_(n-1) ways.

Reverting to the problem of runs, suppose we have a alphas and b 
betas, then there are (a+b)_C_(a) distinguishable orderings. If there 
are n alpha runs, the number of beta runs is necessarily one of n-1, 
n, n+1. Arranging the a alphas in n runs is equivalent to arranging 
them into n cells, none of which is empty, and this can be done in 
(a-1)_C_(n-1) ways. (See the r stars and n cells problem above). It 
follows that with n alpha runs and n+1 beta runs there are           
(a-1)_C_(n-1)*(b-1)_C_(n) arrangements. The number of unlike 
neighbours in this case is (n)+(n+1)-1 = 2n.

From here it would be necessary to find the probability of 1 up to 7 
runs (of boys) with associated n-1, n, n+1 runs of girls in each case.  
For example, the probability of 2 runs of boys is the sum of

2 runs boys 1 run girls      number of unlike neighbours = 2
2 runs boys 2 runs girls                "                = 3
2 runs boys 3 runs girls                "                = 4

Prob (2 runs boys, 1 run girls) = {6_C_1 * 12_C_0}/(20_C_7)

So there is a lot of rather tedious work invoved in finding the 
expected number of unlike neighbours. I hope, however, that the method 
is clear from here.

-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/