1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics - No two together

  1. Oct 30, 2014 #1
    1. The problem statement, all variables and given/known data
    In how many ways can m men and n women be arranged such that no two women are besides each other?
    (m > n)


    2. Relevant equations


    3. The attempt at a solution
    The given answer is m! x P(m + 1, n). I understood how the answer should be a multiple of m!. I also understood that there should be an n in P(m + 1, n). What I couldn't get was how do we get the m + 1 part?
     
  2. jcsd
  3. Oct 30, 2014 #2

    RUber

    User Avatar
    Homework Helper

    Perhaps this is mathematically equivalent to something else that could make more intuitive sense. Have you tried computing for small examples? m = 3, n = 2?
    You would have
    mmwmw
    mwmwm
    wmwmm
    wmmwm
    mwmmw
    wmmmw
    as your permutations, then multiplied by the number of orderings.
    Do a couple more and see if the math works out, maybe you will spot your own pattern.
     
  4. Oct 30, 2014 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    It doesn't say, but this seems to refer to arrangement in a straight line, not a circle.
    I approach this class of problems by reducing to one that has no such constraint.
    First, treat men as identical and women as identical. We can fix that up later by multiplying by the appropriate factorials.
    Suppose you have a valid arrangement. The women in the line partition the set of men into subsets (how many?). What constraint is there on the size of each subset (it's not the same for all of them)? Where the constraint is >= 1, throw a man away. How many men are left? How many ways are there of carving them into the right number of partitions of >= 0 each?
    To show the technique is valid, you need to see that there is a 1-1 mapping between solutions to the reduced problem and those to the original one. We have the mapping one way. To go the other, just insert one man into every partition that should have at least one.
     
  5. Oct 31, 2014 #4
    A friend told me this approach : First, let us consider filling all the men. We will fill them with a gap between each one of them so that we can fill the women there. Now, if we fill them in such a way, there will be m - 1 gaps. Now, add two imaginary places at each end. So, now there are m + 1 places. Fill the women in those places and if there are any women on those imaginary gaps, shift them in and in this way we will reach the answer.

    Is that correct?
     
  6. Oct 31, 2014 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, that's an excellent method - though I didn't understand the bit "if there are any women on those imaginary gaps, shift them in". What is meant by shifting them in? Seems to me the job is done.
     
  7. Oct 31, 2014 #6
    It is to simplify things. Like after all those gaps are imaginary. So, if you have placed the first man on the first seat and then all others with a gap in between, you don't have to work what will be the case then. Just first arrange the women in the seats including the imaginary ones. If you place them on the imaginary ones, then there will be places in between which are empty because m + 1 > n. So, now shift them from the imaginary ones to the empty real ones.
     
  8. Nov 1, 2014 #7

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I don't follow this logic. The way I'd look at it is. First, you place the n men:

    - M - M - M ... - M -

    Each dash (-) represents a place where a woman could stand. There are (m+1) such places and n women, so ##\binom{m+1}{n}## possibilities.
     
    Last edited: Nov 1, 2014
  9. Nov 1, 2014 #8
    Yes. That is what I am trying to say.

    And according to the question it is P(m + 1, n) and not P(n + 1, m).
     
  10. Nov 1, 2014 #9

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, got n and m mixed up. Corrected now.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics - No two together
  1. Combinatorics questions (Replies: 16)

Loading...