Results 1 to 3 of 3

Math Help - Permutations with ordering constraints

  1. #1
    ppp
    ppp is offline
    Newbie
    Joined
    May 2011
    Posts
    3

    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.
    Last edited by ppp; May 18th 2011 at 10:28 PM. Reason: fixed an error
    Follow Math Help Forum on Facebook and Google+

  2. #2
    ppp
    ppp is offline
    Newbie
    Joined
    May 2011
    Posts
    3
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    ppp
    ppp is offline
    Newbie
    Joined
    May 2011
    Posts
    3
    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 {g}_{1} and {r}_{1}. If there happens to be another red ball {r}_{2} in the set then there is a bunch of permutations where the pair ( {g}_{1} {r}_{1} ) does not occur but ( {g}_{1} {r}_{2} ) 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 ( {g}_{i} {r}_{j} ) 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Well Ordering
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: September 8th 2010, 04:04 AM
  2. Constraints
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 27th 2009, 04:53 AM
  3. Well-Ordering
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 08:13 AM
  4. well ordering
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 17th 2008, 10:16 AM
  5. Value with constraints
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: January 23rd 2007, 04:52 AM

Search Tags


/mathhelpforum @mathhelpforum