1. Limited time only! Sign up for a free 30min personal 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!

Various combinatorial analysis problems involving ordering of groups

  1. Sep 17, 2010 #1
    This particular problem has me stumped. I've looked through all the equations given in the book, but none seem to fit this problem correctly. Instead, I tried solving it logically, but I'm stuck on what seems to be the last step of every part. Any help is appreciated!

    1. The problem statement, all variables and given/known data
    Let's say that there are 8 people to be seated in a row.
    1. if there are 4 men and 4 women, and no 2 men or 2 women may sit next to each other, how many ways can they be seated?
    2. if there are 5 men and they must sit next to each other, how many ways can the people be seated?
    3. if there are 4 married couples and each couple must sit next to each other, how many ways can this be done?


    2. Relevant equations
    The basic counting principle, and other combinatorics equations such as n taken r times, and the division of n into r distinct groups by [tex]\frac{n!}{n_{1}!*n_{2}!...n_{r}!}[/tex].


    3. The attempt at a solution
    1)
    To visualize the problem, I wrote out the seating arrangements as such:
    (M1 W1) (M2 W2) (M3 W3) (M4 W4)

    Keeping in mind that no two men or women may sit next to each other. In this sense, there are 4! combinations of women, and 4! combinations of men. Multipling [text]4! * 4![/tex] yields 576 combinations. However, the answer in the book is 1152 combinations. I think I might be missing a step here.

    2)
    Like before, I wrote out the seating arrangement in such a manner:
    (M1 M2 M3 M4 M5) W1 W2 W3

    where M represents a man and W a woman. Now, there are 5 men, so the number of ways to order them is 5!. Likewise, with 3 women, they can be ordered in 3! ways. However, I'm not sure how to relate the two values to each other. That is, I know that for every combination of men, there is a combination of women. Multipling [tex]5! * 3![/tex] only gets me half way to the solution, which is 2280.

    3)
    This seems to be similar to part 1. I ordered the men and women as in the diagram in the first part, and since these are couples, I reasoned the solution to be this:
    There are 4 pairs, so they can all be arranged in 4! ways. Since there are no restrictions on the ordering of men next to women or men next to men, each couple can sit in 2! ways (that is, husband first or wife first in the left-most seat). Therefore, [tex]4! * 2![/tex] yields 48 ways. However, the solution is 384.

    It seems that somewhere along the way I missed a key idea. Can someone point me in the right direction? Thank you!
     
  2. jcsd
  3. Sep 17, 2010 #2

    silvermane

    User Avatar
    Gold Member

    For if there are 4 men and 4 women, and no 2 men or 2 women may sit next to each other, how many ways can they be seated, did you take into account where the first person sits?

    Say we have 8 seats like so:

    XX XX XX XX

    First, we need to choose where the men are sitting. Are they sitting on the left grouping, or are they sitting on the right grouping?
    Here, you've said:

    MF MF MF MF

    and considered the cases for combinations of already chosen "male" and "female" seats; but what about if we switched them and said:

    FM FM FM FM,

    Isn't this another way?

    Thus, you were correct when you said,

    4! * 4!, but you're missing something.... hope this hint helps for no. 1
     
  4. Sep 17, 2010 #3

    silvermane

    User Avatar
    Gold Member

    2.) What you're forgetting here is similar to number 1. Did you consider the cases where we have:

    W MMMMM W W
    W W MMMMM W
    W W W MMMMM

    Because those are also correct ways to seat the men and women such that they are seated beside each other. If you notice, these are 3 completely different ways! Hint: How do these pertain to what you're counting? I'm going to give you less hints as we go, because they build off each other. If you need clarification, just quote and ask :)
     
  5. Sep 17, 2010 #4
    Aha, I see! So for (1) I would have to multiply by 2! for the inverted combinations of men and women pairs, so [tex]4! * 4! * 2![/tex] = 1152. Likewise for (2), there would be a total of 4 different seating arrangements as you mentioned, so that means [tex]5! * 3! * 4[/tex] = 2880.

    I think I'm starting to see what I missed in my calculations. I'll see what I can come up with for part (3). Thank you for you help btw! :) This should clear up my understanding.
     
  6. Sep 17, 2010 #5

    silvermane

    User Avatar
    Gold Member

    :cool: I'm glad to be of service! I remember taking that class long agooo, and it was fun but rigorous :confused:

    If you ever need any help in combinatorial homework/proofs/identities etc, just pm me or post on my wall too :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook