OUR

Combinatorics - Basic Counting Principle for Linear Arrangements

In the previous 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?

0 Comments

Leave a Comment

(Login required to leave a comment.)