# Probability that the given students are not sitting adjacent to each other

Please note that I am not looking for a complete answer, but only hints on how to start. If you want to add a complete solution to help others who might want to know it, please put it in spoiler tags using >!. Thanks!

I am trying to solve this problem, which says:

There are five students $$S_1, S_2, S_3, S_4$$ and $$S_5$$ in a music class and for them there are five seats $$R_1, R_2,R_3,R_4$$ and $$R_5$$ arranged in a row. For $$i=1,2,3,4$$, let $$T_i$$ denote the event that the students $$S_i$$ and $$S_{i+1}$$ do not sit adjacent to each other.

Then the probability of the event $$T_1 \cap T_2 \cap T_3 \cap T_4$$ is:

I understand that it has something to do with derangement theorem, but am not able to proceed as there will be two positions for every $$S_{i+1}$$th student to be adjacent to $$S_i$$th student.

Any help is appreciated!

• This is an Inclusion-Exclusion Principle problem. Do you know how to calculate the number of arrangements in which students $S_i$ and $S_{i + 1}$ are next to each other? Also, you type >! to hide material written in a box. – N. F. Taussig May 24 at 21:51
• @N.F.Taussig I can calculate if two students say $S_1$ and $S_2$ will always be adjacent and it didn't matter if say $S_2$ is adjacent to $S_3$ or not. But it isn't the case here. (And thanks for pointing out the correct syntax. Edited it.) – Eagle May 24 at 22:08

$$T_1 \cap T_2 \cap T_3 \cap T_4$$ represents the number of ways that student $$S_i$$ does not sit next to student $$S_{i + 1}$$, $$1 \leq i \leq 4$$.

One way to compute this is to subtract the number of arrangements in which student $$S_i$$ is adjacent to student $$S_{i + 1}$$ from the total number of arrangements.

Since each student is different, there are $$5!$$ ways to arrange them in a row.

By De Morgan's law, $$|T_1 \cap T_2 \cap T_3 \cap T_4| = 5! - |T_1' \cup T_2' \cup T_3' \cup T_4'|$$ where $$T_i'$$ is the complement of $$T_i$$, $$1 \leq i \leq 4$$. the Inclusion-Exclusion Principle, \begin{align*} |T_1' \cup T_2' \cup T_3' \cup T_4'| & = |T_1'| + |T_2'| + |T_3'| + |T_4'|\\ & \quad - |T_1' \cap T_2'| - |T_1' \cap T_3'| - |T_1' \cap T_4'| - |T_2' \cap T_3'| - |T_2' \cap T_4'| - |T_3' \cap T_4'|\\ & \quad + |T_1' \cap T_2' \cap T_3'| + |T_1' \cap T_2' \cap T_4'| + |T_1' \cap T_3' \cap T_4'| + |T_2' \cap T_3' \cap T_4'|\\ & \quad - |T_1' \cap T_2' \cap T_3' \cap T_4'| \end{align*}

$$|T_1'|$$: This means students $$S_1$$ and $$S_2$$ are adjacent. We have four objects to arrange: $$S_3$$, $$S_4$$, $$S_5$$, and a block containing $$S_1$$ and $$S_2$$. The four objects can be arranged in $$4!$$ ways. The students $$S_1$$ and $$S_2$$ can be arranged in $$2!$$ ways within the block. Hence, there are $$4!2!$$ such arrangements.

By symmetry, $$|T_1'| = |T_2'| = |T_3'| = |T_4'|$$.

$$|T_1' \cap T_2'|$$: This means student $$S_1$$ is adjacent to $$S_2$$ and student $$S_2$$ is adjacent to $$S_3$$. Observe that this means that $$S_2$$ must be flanked on one side by $$S_1$$ and on the other side by $$S_3$$. In this case, we have three objects to arrange: $$S_4$$, $$S_5$$, and the block of three students consisting of $$S_1$$, $$S_2$$, and $$S_3$$. Arrange the objects, then arrange the students in the block, keeping in mind that $$S_2$$ must be in the middle of the block.

The three objects can be arranged in $$3!$$ ways. Since $$S_2$$ must be in the middle of the students in the block, the students in the block can be arranged in $$2!$$ ways. Thus, there are $$3!2!$$ such arrangements.

By symmetry, $$|T_1' \cap T_2'| = |T_2' \cap T_3'| = |T_3' \cap T_4'|$$.

$$|T_1' \cap T_3'|$$: This means students $$S_1$$ and $$S_2$$ are adjacent and students $$S_3$$ and $$S_4$$ are adjacent. Thus, we have three objects to arrange: $$S_5$$, the block containing $$S_1$$ and $$S_2$$, and the block containing $$S_3$$ and $$S_4$$. Arrange the objects. Arrange the students within each block.

The objects can be arranged in $$3!$$ ways. The students within each block can be arranged in $$2!$$ ways. Thus, there are $$3!2!2!$$ such arrangements.

By symmetry, $$|T_1' \cap T_3'| = |T_1' \cap T_4'| = |T_2' \cap T_4'|$$.

$$|T_1' \cap T_2' \cap T_3'|$$: This means students $$S_1$$ and $$S_2$$ are adjacent, students $$S_2$$ and $$S_3$$ are adjacent, and students $$S_3$$ and $$S_4$$ are adjacent. Observe that student $$S_2$$ must be flanked on one side by $$S_1$$ and on the other by $$S_3$$ and that student $$S_3$$ must be flanked on one side by $$S_2$$ and on the other by $$S_4$$. Therefore, we have two objects to arrange: $$S_5$$ and the block containing the other four students. Arrange the objects, then arrange the students within the block.

There are $$2!$$ ways to arrange the objects and $$2!$$ ways to arrange the students within the block since the only possible arrangements within the block are $$S_1, S_2, S_3, S_4$$ or $$S_4, S_3, S_2, S_1$$. Hence, there are $$2!2!$$ such arrangements.

By symmetry, $$|T_1' \cap T_2' \cap T_3'| = |T_2' \cap T_3' \cap T_4'|$$.

$$|T_1' \cap T_2' \cap T_4'|$$: This means students $$S_1$$ and $$S_2$$ are adjacent, students $$S_2$$ and $$S_3$$ are adjacent, and students $$S_4$$ and $$S_5$$ are adjacent. Therefore, we have two objects to arrange, the block containing $$S_1$$, $$S_2$$, and $$S_3$$ and the block containing $$S_4$$ and $$S_5$$. Arrange the objects, then arrange the students within the blocks, keeping in mind the position of $$S_2$$ within that student's block.

There are $$2!$$ ways to arrange the block and $$2!$$ ways to arrange the students within each block. Hence, there are $$2!2!2!$$ such arrangements.

By symmetry, $$|T_1' \cap T_2' \cap T_4'| = |T_1' \cap T_3' \cap T_4'|$$.

$$|T_1' \cap T_2' \cap T_3' \cap T_4'|$$: This means students $$S_1$$ and $$S_2$$ are adjacent, $$S_2$$ and $$S_3$$ are adjacent, $$S_3$$ and $$S_4$$ are adjacent, and $$S_4$$ and $$S_5$$ are adjacent. Thus, $$S_2$$ is flanked on one side by $$S_1$$ and on the other side by $$S_3$$, $$S_3$$ is flanked on one side by $$S_2$$ and on the other side by $$S_4$$, and $$S_4$$ is flanked on one side by $$S_3$$ and on the other side by $$S_4$$. Consequently, the students form a single block. Arrange the students within that block.

Since the students must appear in the order $$S_1, S_2, S_3, S_4, S_5$$ or its reverse, this can be done in $$2!$$ ways.

Finally, apply the above formulas to calculate the number of favorable cases, then divide by the $$5!$$ possible arrangements.