# Thread: number of possible combinations...

1. ## 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 $\displaystyle 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 :

$\displaystyle (n!/(n-2)!) * (n+1)/(n-1)$

and i can't figure out how to logicaly deduce that $\displaystyle (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!

2. Originally Posted by kodai
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 $\displaystyle 2\left[(N-1)!\right]$ is your answer.

3. 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.

4. Originally Posted by kodai

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"}.