Results 1 to 4 of 4

Math Help - number of possible combinations...

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    5

    number of possible combinations...

    Ok so here's the problem...

    Suppose there are N people, and N chairs to seat them, all in a row. There are, however, 2 people (who we will call bob and row) who will only sit next to each other. That means that if bob sits in the 11th seat, then row must sit next to him, in either the 10th or 12th. this also means that if one of them (bob or rowdy, but we'll just say bob for example) is sitting in either of the last seats, then rowdy must sit in either n-1 if bob is sitting in the n'th seat (since n+1 doesn't exist) or in 2 if bob is sitting in 1 (since 0 doesn't exist).

    so, how many possible combinations of N people, if 2 wish to sit next to each other.

    I couldn't figure out a logical answer, but after allot of enumeartion (which i know is not the correct way to do things, but it can sometimes steer you in the right way) i came up with n!/(n-2)!

    however, when i try to prove this with induction (the only way we know how to formally prove currently) i get stuck when trying n+1 with :

    (n!/(n-2)!) * (n+1)/(n-1)

    and i can't figure out how to logicaly deduce that (n+1)/(n-1) will give us the next set of iterations.

    anyway, the main question is the first one about number of combinations, the second is just a curiosity- since i'm sure we weren't supposed to prove this using induction. Thanks allot! I really appreciate your help, and if you could, please explain! it's probably very simply, but I just can't put my finger on it.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,910
    Thanks
    1759
    Awards
    1
    Quote Originally Posted by kodai View Post
    Suppose there are N people, and N chairs to seat them, all in a row. There are, however, 2 people who will only sit next to each other, so, how many possible combinations of N people, if 2 wish to sit next to each other.
    Please do not over simplify the question!
    If you have two who must be together, you have (N-1) packets,
    But one of those packets can be seated in 2 ways.
    So 2\left[(N-1)!\right] is your answer.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    5
    Thank you so much for your answer! It seems to work!

    But, i'm a little confused on how you arrived to it. What do you mean packets?

    Did you get the two because: [bob][row] and [row][bob] ?


    Thanks! And sorry for asking you to break it down so much, this is my first semester in Discrete math and I'm having allot of trouble.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,206
    Thanks
    1789
    Quote Originally Posted by kodai View Post
    Thank you so much for your answer! It seems to work!

    But, i'm a little confused on how you arrived to it. What do you mean packets?

    Did you get the two because: [bob][row] and [row][bob] ?


    Thanks! And sorry for asking you to break it down so much, this is my first semester in Discrete math and I'm having allot of trouble.
    No, the "packets" are {Bob and Bill}, the two people who MUST sit together, and each of the other people individually. Since there are n people, treating "Bob and Bill" as one "packet" (perhaps it would be simpler to just think of them as one "person") there are n-1 "people" to be seated and there are, of course, (n-1)! ways to do that. Now the "2" comes from the fact that the "Bob and Bill" "packet" or "person" could be seated either "Bob, Bill" or "Bill, Bob": 2(n-1)!

    If you are still not clear, try some simple examples. If, in fact, the only two people were Bob and Bill, then n= 2 and 2(n-1)!= 2(1!)= 2 and the two orders are "Bob, Bill" and "Bill, Bob".

    If there were three people, say, "Bob", "Bill", and "Clarise", and "Bob" and "Bill" must sit together, n= 3 so 2(n-1)!= 2(2!)= 4. If we treat the "Bob" and "Bill" "packet" as "B" we have 2 "packets": "B" and "Clarise" and the 2!= 2 ways of ordering them are {"B", "Clarise"} and {"Clarise", "B"}. But we can replace "B" with either {"Bill", "Bob"} or {"Bob", "Bill"} so the 4 ways of seating the three people are {"Bill", "Bob", "Clarise"}, {"Bob", "Bill", "Clarise"}, {"Clarise", "Bill", "Bob"}, and {"Clarise", "Bob", "Bill"}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of combinations.
    Posted in the Statistics Forum
    Replies: 5
    Last Post: July 27th 2011, 06:31 PM
  2. Number of combinations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 28th 2011, 03:11 PM
  3. number of combinations possible
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 25th 2009, 09:28 AM
  4. number of combinations
    Posted in the Statistics Forum
    Replies: 2
    Last Post: August 14th 2008, 10:11 AM
  5. number of combinations
    Posted in the Statistics Forum
    Replies: 3
    Last Post: May 14th 2008, 07:29 PM

Search Tags


/mathhelpforum @mathhelpforum