Quarter Wit, Quarter Wisdom: Circular Arrangement Constraints – Part II

Quarter Wit, Quarter WisdomWith today’s post, let’s wrap up arrangements for the time being. We will discuss some complex circular arrangement constraints (which we will easily work through) today and start with combinations (i.e. picking “r” units out of “n” units) next week. Thereafter we will look at questions involving both, picking and arranging (yeah, that will be fun!).

Question 1: A group of 8 friends sit together in a circle. If A refuses to sit beside B unless C sits on the other side of A as well, how many possible seating arrangements are possible?

Solution: Let’s start with what we know. We know that the total number of ways in which 8 people can be arranged around a circular table is (8-1)! = 7!

Since we do not want A to sit next to B, let’s try and make them sit together. This will give us the number of arrangements that are unacceptable to us. Let’s say that A and B are a single unit. So now there are 7 units which need to be arranged in a circle. This can be done in (7-1)! = 6! ways. Since there are two arrangements possible, AB and BA, within the unit, we need to multiply 6! by 2.

Number of arrangements in which A and B sit together = 2*6!

We can subtract these ‘unacceptable arrangements’ from total arrangements to get the number of ‘acceptable arrangements’. But this number of ‘unacceptable arrangements’ includes those arrangements where C is sitting on the other side of A. But those arrangements are acceptable to us so we should not subtract them out. How many such arrangements are there in which A and B are sitting together and C is sitting beside A too?

Now C, A and B form a single unit leaving us with 6 units to be arranged in a circle. 6 units can be arranged in (6-1)! = 5! ways

CAB can also be arranged as BAC, hence the 5! needs to be multiplied by 2. (Mind you, we will not consider ABC, ACB etc here since A should be in the middle)

Number of arrangements in which A and B sit together and C sits beside A = 2*5!

Therefore, number of unacceptable arrangements = 2*6! – 2*5!

We subtract these out of the total number of arrangements and we get the total number of acceptable arrangements.

Possible number of seating arrangements = 7! – (2*6! – 2*5!) = 3840

If you are wondering about the ‘painful’ calculation involved in the step above, don’t worry. Calculations with factorials are generally quite straight forward.

7! – (2*6! – 2*5!) = 7! – 2*6! + 2*5!

= 2*5! (21 – 6 + 1) (Take 2*5! common out of the three terms)

= 2*120*16 = 32*120 = 3840

I hope the solution makes sense to you. Let’s look at another tricky circular arrangement problem.

Question 2: Seven men and seven women have to sit around a circular table so that no two women are together. In how many different ways can this be done?

Solution:
There are 7 men: Mr. A, Mr. B, Mr. C, Mr. D …
and 7 women: Ms. A, Ms. B, Ms. C, Ms. D …

Let’s say we have 14 identical chairs around the round table.

We need to seat the 7 women such that no two of them are together i.e. there should be a man on either side of every woman. Since there are exactly 7 men, the women and men should sit alternately. Let’s make the women sit first.  For the first woman who sits, each seat is identical so she sits in one way (say Ms.C takes a seat). Now each seat is distinct relative to this woman (Ms. C). There are 7 seats identified for men (e.g. seats right next to Ms. C and every alternate seat) and 6 for the remaining 6 women. The 7 men can occupy the 7 distinct seats in 7! ways and the 6 women can occupy the 6 distinct seats in 6! ways.

Total number of arrangements = 6!*7!

Something to ponder upon: The total number of arrangements is not 13!. Why?

Question 3: Find the number of ways in which four men, two women and a child can sit at a circular table if the child is seated between the two women.

Solution:

We have 7 people and 7 seats around a circular table.

First let’s make the child sit anywhere in one way since all the places are identical. The two women can sit around the child in 2! ways. Now we have 4 distinct seats (relative to the people sitting) left for the 4 men and they can occupy the seats in 4! ways.

Total number of arrangements = 1*2!*4! = 48

Things to ponder upon:

Case 1: Same question as above but the chairs are numbered i.e. all the seats are distinct. Find the number of ways in which four men, two women and a child can sit around a circular table with numbered seats if the child is seated between the two women.

Case 2: Same question as above but they need to stand in a row instead. Find the number of ways in which four men, two women and a child can stand in a row if the child is standing between the two women.

Are the two cases above equivalent?

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 GMAT prep for Veritas Prep and regularly participates in content development projects such as this blog!

9 Responses

  1. Krishna says:

    Hello Karishma – how are you?
    I guess these are the posts you were mentioning in GC when answering the advanced combinatorial variants.
    Qn. 2 – the circular arrangement applies for distinct items. Here you have 7 identical men and 7 identical women. So taking the collection of men as 1 set and women as 2nd sets, we have 2 distinct folks sitting around a circle in (2-1) factorial = 1!
    7 men can sit in 7 seats in 7! Ways
    7 women can sit in 7 seats s.t. none of the women sit next to each other in (7-2+1)! = 6! Ways

    So, total = 7! * 6! Ways

    Q.2. – we can approach in the same way. It will be very easy.

  2. SonyGmat says:

    I believe the 2 cases are equivalent. In Case 1 since the chairs are numbered it is the same as if it were a linear arrangement like Case 2.

    In both the answer is 5! x 2

    • Karishma says:

      Ok, let’s say the seats are numbered from 1 to 7. In case 1, the child can sit on any of the 7 seats. What about in case 2? Can the child take position 1? or position 7 for that matter?

  3. Prasath says:

    case1: 6*2*3!
    case2: 5!*2

    wow this is so interesting. I somehow found the slot method way easier to solve circular arrangement problems. Thinking about how many of the seats can be occupied by a certain person and then multiplying these numbers gets me to the right answer much faster than thinking about total arrangements is x!… now subtract those cases who break the restriction… to break the restriction think the other way… but because of the circular arrangement it gets even harder to figure out the opposite cases.

    but i agree in linear arrangement problems this approach is very helpful.

    thank you by the way of all these posts. I have two books from veritas. The combinatorics and the advanced problems one. You focus on the high-end kind of question, where prep material is scarce. Really enjoying reading your posts-

    • Karishma says:

      Thanks. I am glad you find the posts enjoyable. As for case 1 and case 2 -

      When all the seats are distinct in circular arrangement (case 1), the number of arrangements will be 7*2!*4! = 336.
      Make the child sit on any one of the 7 seats since all are unique now. Whenever he takes a different seat, we get a new arrangement. When he sits on seat number 1, it’s a different arrangement. When he sits on seat number 2, it’s a different arrangement etc. The women sit around the child in 2! ways and the men sit on the rest of the 4 seats in 4! ways. (as before)

      In case of linear arrangement (case 2), the number of arrangements will be 5!*2 = 240.

      We have 96 extra arrangements in case 1 because the child can take seat no 1 and 7 in that case (2*2!*4! = 96 extra cases)

  4. Prasath says:

    Rereading your blog, just great.

  5. Rohit says:

    Hi Karishma

    In case 2, you have mentioned the solution to be 2*5!. Now i was just wondering as to what 2 & 5! would signify ? Say would 2 be the position of the women and 5! be the number of way of arranging the 1 kid and 5 men ? I want to clarify if I am thinking this problem along the right lines.

    Lastly your posts are much appreciated :)

    • Karishma says:

      In case 2, you have to arrange 4 men and a group which you can do in 5! ways. The group consists of two women and a child between them. The two women can be arranged around the child in 2 ways. So total ways = 2*5!

Leave a Reply

Spam protection by WP Captcha-Free