0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – N. F. Taussig May 24 at 21:51
  • $\begingroup$ @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.) $\endgroup$ – Eagle May 24 at 22:08
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.