Thread: Permutations with ordering constraints

Hello,

Let's say we have a set of n balls, consisting of m green balls, l red balls and k grey balls (so, m+l+k=n). The balls will be arranged in some order, using all of the n balls.

I would like to calculate the probability that if the balls are ordered randomly, a green ball is followed by a red ball at least once. I was able to find an approximate solution using probabilities: assume that at any position, the probability of a green ball occuring there is m/n and the probability of a red ball occuring is l/n. Then I can find the probability I am looking for by adding the probabilities of green and red occuring at positions 1 and 2 respectively, to positions n-1 and n.

While this is fairly easy, it is also incorrect as the events of each color occuring at a position are not exactly independent events (for example, if the assumed probability of a green ball being at any position m/n>0 then there is also a non-zero probability that all balls are green, which contradicts our problem statement in cases where 0<m<n).

The correct way appears to be to count all the permutations of this set of n balls, where a green ball is at a position i and a red ball is at a position i+1. The probability of this event is then (number of such permutations)/n!.

So, on to my questions:
1. How would one approach calculating the number of permutations that satisfy these ordering constraints?
2. --edited--

Thank you.

Giving it some further thought, I came up with this:

Since the constraint is that a red ball follows a green ball once or more, I will take one red ball and one green ball from the set and make a fixed group of them which will be treated as one item. n-2 balls that may be red, green or gray (depending on values of m, l, k) will remain and my set now has n-1 items. A permutation would then look something like x (g r) x x x x.

Looking at this, it appears that the item (g r) has n-1 possible positions and the remainder of balls may be arranged in (n-2)! ways. So it looks like the number of permutations that have a red ball following a green ball once or more is (n-1)(n-2)! = (n-1)!

So the probability I'm looking for can be calculated as (n-1)!/n! = 1/n (if m>0 and l>0; in cases where m=0 or l=0 the probability is 0). Could this be correct?

I suppose I should add my further insights on the subject, even though I am responding to my own posts.

The solution 1/n is very counter-intuitive. Casually, it looks quite suspicious that the probability would not be dependent on values of m and l. Sure enough, with a pen and paper it is quite easy to verify that it is not correct for n=3 and n=4 (even though, for the special case of m=1 and l=1, 1/n is correct).

So I re-examined my reasoning in the second post of this thread and realized that when picking a green and red ball from the set, what I actually get is balls and . If there happens to be another red ball in the set then there is a bunch of permutations where the pair ( ) does not occur but ( ) does.

To get the number of permutations we're interested in, all of the combinations of red and green balls should be considered. There is m*l of such combinations and each of them should contribute (n-1)! permutations that satisfy the constraint given.

Unfortunately, for the general case, there will be instances where several ( ) pairs are present in one permutation. The number of these shared instances should be subtracted from m*l*(n-1)!, but finding that number seems to require some sort of iterative process - if it is computationally expensive then it may become significant up to which value of n the probability can be calculated practically.