Quarter Wit, Quarter Wisdom: Linear Arrangement Constraints – Part I

Quarter Wit, Quarter WisdomLet me first give you the solution to the question I gave you in my last post:

Question: In how many different ways (relative to each other) can 8 friends sit around a square table with 2 seats on each side of the table?

Solution: What happens when the first friend enters the room? Are all the seats same for him?



Are the seat numbers 5 and 6 the same for him? (The seats are not actually numbered. We have numbered them for easy reference.)

No, they are not! Seat no. 5 has a corner (of the table) on the right hand side and an empty chair on the left hand side while seat no. 6 has a corner on the left hand side and an empty chair on the right hand side. So then, are all the seats distinct for him? I am sure you agree that they are not. It is similar to a circle situation but not quite. Seat no. 6 and seat no. 4 are alike since they both have a corner on the left hand side and an empty chair on the right hand side.

Isn’t the case the same for seat numbers 2 and 8 as well? Can I say that the seat numbers 2, 4, 6 and 8 are the same? It doesn’t matter on which seat he sits out of these 4; the arrangement stays the same. Similarly, notice that seat numbers 1, 3, 5 and 7 are also the same. Therefore, there are 2 ways in which the first person can sit. He can either sit on one of 1, 3, 5 and 7 or on one of 2, 4, 6 and 8. After he sits, all the remaining 7 seats are distinct. 7 people can sit on 7 distinct seats in 7! ways.

Total number of arrangements = 2*7!

Hope it makes sense to you, especially for GMAT prep purposes. You can try any number of variations now. You can also try putting in constraints. I will focus on constraints in linear arrangements today. Perhaps, in another post, we can look at constraints in circular arrangements. In the first post on combinatorics, we learned the basic counting principle. Using that we can solve many simple questions for example:

Question 1: In how many ways can 3 people sit on 3 adjacent seats of the front row of the theatre?

We know that it is a straight forward basic counting principle application. On the leftmost seat, a person can sit in 3 ways (choose any one of the 3 people). On the middle seat, a person can sit in 2 ways (since 1 person has already been seated). There is only 1 person left for the rightmost seat so he can sit there in 1 way. Total number of arrangements = 3*2*1 = 3! = 6

Now, let’s try to add some constraints here. I will start will some very simple constraints and go on to some fairly advanced constraints.

Question 2: In how many ways can 6 people sit on 6 adjacent seats of the front row of the theatre if two of them, A and B, cannot sit together?

Solution: This is a very simple constraint question. First tell me, what if there was no constraint i.e. what is the total number of arrangements in which 6 people can sit in a row? You should know by now that it is 6! (using Basic Counting Principle). Now, rather than counting the number of ways in which they will not sit next to each other, we can count the number of ways in which they will sit next to each other and subtract that from the total number of arrangements. Why? Because it is easier to group them together (think that we have handcuffed them together) and treat them as a single person to get the arrangements where they will sit together.

So let’s deal with a different question first: In how many ways can 6 people sit on 6 consecutive seats of the front row of the theatre if two of them, A and B, must sit together?

There are 5 individuals/groups: AB C D E F

These 5 can be arranged in a line in 5! ways. But the group AB itself can be arranged in 2 ways AB or BA i.e. B could be to the right of A or to the left of A.

Total number of arrangements = 2*5! (Notice the multiplication sign here. We have to arrange the 5 individuals/groups AND A and B.)

This is the number of arrangements in which A and B will sit together.

Therefore, the number of arrangements in which they will not sit together = 6! – 2*5!

Now let’s discuss some trickier variations of this question.

Question 3: 7 people, A, B, C, D, E, F and H, go to a movie and sit next to each other in 8 adjacent seats in the front row of the theatre. A and F will not sit next to each other in how many different arrangements?

Solution: Here, there is an additional vacant spot since there are only 7 people but 8 seats. You might think that it is a little confusing since you will need to deal with the vacant spot separately. Actually, this be done in a very straight forward way.

7 people including A and F have to be seated such that A and F are not next to each other. So an arrangement where A and F have the vacant spot between them is acceptable. I will just imagine that there is an invisible person called Mr. V. He takes the vacant spot. If A and F have V between them, that arrangement is acceptable to us. Now this question is exactly like the question above. We have 8 people sitting in 8 distinct seats. 8 people (including our imaginary Mr. V) can sit in 8 seats in 8! arrangements.

A and F can sit together in 2*7! arrangements (similar to question no. 2)

Hence, the number of arrangements in which A and F will not sit together = 8! – 2*7!

Question 4: 7 people, A, B, C, D, E, F and H, go to a movie and sit next to each other in 8 adjacent seats in the front row of the theatre. In how many different arrangements will there be at least one person between A and F?

Solution: This variant wants you to put at least one person between A and F. This means that all those cases where A and F are together are not acceptable and all those cases where A and F have Mr. V (the vacant spot) between them are also not acceptable.
8 people (including our imaginary Mr. V) can sit in 8 seats in 8! ways.

A and F can sit together in 2*7! arrangements (similar to question no. 2). Number of arrangements in which A and F have Mr. V between them = 2*6!

How? Now we group AVF together and consider this group one person. So there are 6 distinct individuals/groups which can be arranged in 6! ways. But we have 2 arrangements in this group: AVF and FVA. So total number of arrangements here = 2*6!

These cases are not acceptable.

Hence, the number of arrangements in which A and F will have a person between them = 8! – 2*7! – 2*6! = 8! – 16*6!

Compare question no. 3 with question no. 4: one where you don’t want them to be together, the other where you don’t want them to be together and you don’t want the vacant spot between them.

Obviously, in the second case, the number of cases you do not want are higher. So you subtract a higher number out of the total number of cases.

Let me leave you with a question now. Make sure you answer exactly what is asked.

Question 5: 6 people go to a movie and sit next to each other in 6 adjacent seats in the front row of the theatre. If A cannot sit to the right of F, how many different arrangements are possible?

Karishma, a Computer Engineer with a keen interest in alternative Mathematical approaches, has mentored students in the continents of Asia, Europe and North America. She teaches the GMAT for Veritas Prep and regularly participates in content development projects such as this blog!