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

Question

_{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!

Answer 1

$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.