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!

14 Responses

  1. Gurvinder says:

    Thank You

  2. SonyGmat says:

    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?

    I count all the possible arrangements: only

    A F 1 2 3 4 —> 4!
    A 1 F 2 3 4 —> 4!
    A 1 2 F 3 4 —-> 4!
    A 1 2 3 F 4 —–> 4!
    A 1 2 3 4 F —-> 4!

    so 4!*5=5!=120

  3. Karishma says:

    I would say using symmetry is the fastest way to deal with this problem. All you have to do is 6!/2.

  4. Kapil says:

    Hey Karishma,
    Not sure if you are still responding to older posts..But Il try.
    First of all, I would like to thank you for posting such useful content on the blog.They are really very informative.

    My question is how do we practice oiur minds to think on the same lines as your s for solutions. for example, once you explain the problem, I get it. But than the question on GMAT would ne new, not same, how do we ensure we have the right aparoch?

    • Karishma says:

      Hey Kapil,
      It’s a great question though I have no easy answer to it. Practice will help. The trick is not to have the fastest/best approach every time (since it will be different for different questions), it is to have multiple approaches in your mind for every type of question. It is to understand the basics really well. Then use the approach that comes first to mind on test day. Sometimes I find myself using two different approaches on the same question on two different days.
      Ensure that your basics are whistle clean and then practice many questions using many different approaches. Pay special attention to how a slight variation in a question can change it completely (especially true for PnC) and hence might change the approach you would use for it.

  5. gp says:

    Hello Karishma, My doubt is about Question 3.

    I prefer the basic counting principle myself. Please explain the solution this way rather than the handcuffed way. Thanks.

    A can sit in 8 ways, F can sit in only 1 way (along with A). There are 6 seats remaining, hence others can sit in 6! ways. We also account for F sitting left or right of A.

    2 x (8×1) x 6!

    • Karishma says:

      Actually the non-handcuffed way is much more complicated.
      A can sit in 8 ways. Depending on where A sits, F can sit in 1 or 2 ways. If A is sitting on a corner seat, F must take the seat next to him. If A is sitting somewhere in the middle, F has two options. So making them sit one by one is more complicated.

  6. gp says:

    Hello Karishma,

    For the fourth question, is my approach right for such problems where there is a vacant seat ? Thanks.

    A and B can have 1 person. 2 persons, or upto 5 people in between – there are 8 seats, so A has 8 choices on the first seat, the next seat has to be somebody other than F – we have 5 choices (5C1), F can now sit in 6 seats. Remaining 4 people can sit in 5 seats in 5x4x3x2 ways.

    8 5 6 5 4 3 2
    _ _ _ _ _ _ _ _

    • Karishma says:

      Actually, I am not very convinced of the logic. A has 8 choices so say he takes a middle seat. What do you mean by the next seat? On which side of A are we talking about? Say B sits to the right of A. F does not have 6 options now. He cannot sit to the left of A or to the left with a vacant seat between him and A.

      • gp says:

        Oh yes, I overlooked a condition when the vacant spot comes in between. Thumbs up to the handcuffed way. Thanks again, Karishma.

        Cases where Vacant Spot is at the beginning or end (Say, vacant spot at Seat 1): Say A sits in a middle seat (8 choices), F cannot sit in seats right or left to A (5 choices), B onwards they can sit in 6! ways leading to my earlier answer 8 x 5 x 6!

        V A F
        _ _ _ _ _ _ _ _

        But I should’ve also considered the case where the vacant spot is in the middle (Seat 3 here) AND next to A:

        F V A
        _ _ _ _ _ _ _ _

        A has 8 choices, F cannot sit at left or right of A (5 choices – Say F chooses Seat 2), one of the remaining 5 people (B, C, D, E, H = 5C1 ways = 5 choices) must choose Seat 3 as we cannot leave a vacant space between A and F and there must be atleast 1 person between A and F. Remaining people can now sit in 5! factorial ways. This gives the final calculation as

        8 x 5 x 5 x 5!

        These are 2 contradicting answers which is why handcuffed way is the right way.

  7. Mike says:

    Hi Karishma,

    Can you please explain how you came up with “8! – 16*6!”? Here is the way I tried to do it: I factored out the (2)(6!) to get (2)(6!)[7-1]=(12)(6!). So I got 8!-(12)(6!).

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

    Thanks.

    • Karishma says:

      8! – 2*7! – 2*6! = 8! – 2*6! (7 + 1) = 8! – 16*6!

      Note that when you take out 2*6! common, you are taking the negative sign out as well (since both terms have the negative sign)

      Alternatively,
      8! – 2*7! – 2*6! = 8! – 2*7*6! – 2*6! = 8! – 14*6! – 2*6! = 8! – 16*6!

Leave a Reply

Spam protection by WP Captcha-Free