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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/