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!

Combinatorics questions

  1. Oct 19, 2015 #1
    1. The problem statement, all variables and given/known data
    Three children, each accompanied by a guardian, seek admission in a school. The principal wants to interview all the 6 persons one after the other subject to the condition that no child is interviewed before its
    guardian. In how many ways can this be done ?

    2. Relevant equations


    3. The attempt at a solution
    So, I read the solution to this problem, because I could only work it out with a lot of casework (I did get the right answer), but this question wasn't supposed to be that time consuming.

    So, here's what I read--
    No. of ways = 6C2 * 4C2 * 2C2 = 90
    That doesn't make much sense to me. Help?
     
  2. jcsd
  3. Oct 19, 2015 #2
    Suppose the 6 people are C1,G1,C2,G2,C3,G3,
    Think of the 6 of them standing in line waiting to see the principal.
    There are 6 positions in which they can stand in the line.
    Choose 2 of the 6 positions in the line for C1 and G1 to stand in, placing C1 behind G1.
    That can be done in 6C2 ways.
    That leaves 4 positions in the line.
    Choose 2 of the remaining 4 positions in the line for C2 and G2 to stand in, putting C2 behind G2.
    That can be done in 4C2 ways.
    That leaves 2 positions in the line.
    Choose 2 of the remaining 2 positions in the line for C3 and G3 to stand in, putting C3 behind G3.
    That can be done in 2C2 "ways". i.e., just 1 way!

    Answer 6C2*4C2*2C2
     
    Last edited: Oct 19, 2015
  4. Oct 20, 2015 #3
    Thanks! That was pretty neat :)
     
  5. Oct 20, 2015 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    It's even easier than that.
    With no constraint, there are 6! orders. In what fraction of those are guardian 1 and child 1 in the right order? Ditto, guardian 2 and child 2? Are those two fractions independent (as in, independent events)? Etc.
     
  6. Oct 23, 2015 #5
    They should be independent, or I could just use symmetry to justify independence. So, that'd be 6!/(2)^3. Which does give the same answer :)
     
  7. Oct 23, 2015 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Exactly. For every arrangement in which G1 precedes C1 there is an otherwise identical arrangement in which C1 precedes G1, just by swapping them. Hence the independence.
     
  8. Oct 24, 2015 #7
    Hmm...why do we not need to multiply the answer by 3! since there are 3 'couples' to chose from when placing them in 6C2 and so forth?
     
  9. Oct 24, 2015 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Which post are you responding to?
     
  10. Oct 24, 2015 #9
    No one in particular, maybe just all of the posts above, since all agreed upon the same solution.
     
  11. Oct 24, 2015 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    My solution in posts #4 and #6 did not involve 6C2, so it can't apply to that. I'll take it as referring to Edwin's solution in post #2.

    Edwin took a particular pair and chose two places in the queue for that pair, then considered the next pair, etc.
    The resulting ordering does not depend on the order in which the pairs were chosen. Any given ordering of the six can result from any ordering of selection of the three pairs. If you were to multiply by the number of orders in which the pairs were selected you would count each ordering of the six six times.
     
  12. Oct 24, 2015 #11
    Oh I see. So his method has covered all possibilities. I have some weakness with combinatorics, especially in cases like this when I don't know if I should multiply the choices of couples or not. I have trouble seeing that the method above has covered all possibilities.

    Anyway, thanks.
     
  13. Oct 24, 2015 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    You're not alone!
     
  14. Oct 24, 2015 #13
    It's nice to know, because it's frustrating. I have invested a lot of time doing lots of problems like this; I've gotten better but it's still not intuitive.

    If you don't mind, can you explain the other solution? I don't understand where the 2^3 come from. Are they the 3 couples grouped together?
     
  15. Oct 24, 2015 #14

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    There are 6! orderings of the six people. In half of these, G1 and C1 are in the wrong order, so rule those out. In half of the remainder, G2 and C2 are in the wrong order, getting us down to 6!/4. Finally, cut out those where G3 and C3 are in the wrong order.
     
  16. Oct 25, 2015 #15
    This solution is new to me, so I have trouble understanding it. When you say that in half of the orderings, G1 and C1 are in the wrong order, is the working suppose to be like this:
    ( 5+4+3+2+1) x 4!

    or is it just common sense? I can't 'see' it.
     
  17. Oct 25, 2015 #16

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Consider any ordering of the six. If G1 and C1 are in the wrong order you can swap them to produce an ordering of the six in which they are in the right order, and vice versa. So there must be the same number of 6-sequences with G1 and C1 in the right order as in the wrong order.
     
  18. Oct 25, 2015 #17
    Ah, ok. Thanks!
     
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 questions
  1. Combinatorics question (Replies: 2)

  2. Combinatorics Question (Replies: 7)

Loading...