Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Probability
High School Permutations and Combinations
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search