Question

A panel is conducting an interview on six candidates of different heights. If they are to put them in line, in how many ways can they arrange them in line such that no three consecutive candidates are in increasing order of height from front to back?

Answer 1

Answer on Question #62439 – Math – Discrete Mathematics

Question

A panel is conducting an interview on six candidates of different heights. If they are to put them in line, in how many ways can they arrange them in line such that no three consecutive candidates are in increasing order of height from front to back?.

Solution

First, note that there are $|X| = 6! = 720$ ways to arrange the candidates.

Next, let $D_n$ be the event that the $n$-th through $n+2$-th candidates are in increasing order of height. We therefore want to find $|X \setminus (D_1 \cup D_2 \cup D_3 \cup D_4)|$.

By the inclusion-exclusion principle we have

$$\begin{array}{l} \left| \left(D_1 \cup D_2 \cup D_3 \cup D_4\right) \right| = \\ = |D_1| + |D_2| + |D_3| + |D_4| \\ - \left(|D_1 \cap D_2| + |D_2 \cap D_3| + |D_3 \cap D_4| + |D_1 \cap D_3| + |D_2 \cap D_4|\right) \\ \left. + |D_1 \cap D_4|\right) \\ \left. + \left(|D_1 \cap D_2 \cap D_3| + |D_2 \cap D_3 \cap D_4| + |D_1 \cap D_2 \cap D_4| + |D_1 \cap D_3 \cap D_4|\right) \right. \\ \left. - |D_1 \cap D_2 \cap D_3 \cap D_4| = \right. \\ = 4 * |D_1| - 3 * |D_1 \cap D_2| - 2 * |D_1 \cap D_3| - |D_1 \cap D_4| + 2 \\ * |D_1 \cap D_2 \cap D_3| + 2 * |D_1 \cap D_2 \cap D_4| - |D_1 \cap D_2 \cap D_3 \cap D_4| = \\ = 4 * |D_1| - 3 * |D_1 \cap D_2| - 2 * |D_1 \cap D_3| - |D_1 \cap D_4| + 2 * |D_1 \cap D_3| \\ + 2 * |D_1 \cap D_2 \cap D_4| - |D_1 \cap D_2 \cap D_4| = \\ = 4 * |D_1| - 3 * |D_1 \cap D_2| - |D_1 \cap D_4| + |D_1 \cap D_2 \cap D_4| \\ = 4 * \binom{6}{3} * 3! - 3 * \binom{6}{4} * 2! - \binom{6}{3} + 1 = \\ = 4 * 20 * 6 - 3 * 15 * 2 - 20 + 1 = 371. \end{array}$$

So $|X \setminus (D_1 \cup D_2 \cup D_3 \cup D_4)| = |X| - |(D_1 \cup D_2 \cup D_3 \cup D_4)| = 720 - 371 = 349$.

Answer: 349.

www AssignmentExpert.com