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 #62186 – Programming & Computer Science - MatLAB |Mathematica | MathCAD | Maple

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.

Let $x_n$ - number of incorrect ranks of length $n$. We seek recurrence for $x_n$.

Consider the length of the wrong rank $n+1$ ($n>1$). Let $Z$ - the highest candidate in the line. It can stand on anywhere from 1 to $n+1$ (enumerate candidates left to right).

Assume that $Z$ stands for $(k+1)$-th place ($k = 0, 1, \ldots, n$); ie, to the left of $Z$ are $k$ candidates (which you can choose $C_n^k$ ways), and the right of $Z$ are the remaining $n-k$ candidates.

Note that the left of $Z$ is the length of the $k$ rank wrong, but not arbitrary, as such, whose penultimate candidate $X$ above the last candidate $Y$ (otherwise the candidates $X$, $Y$ and $Z$ will increase on standing). It is clear that these ranks is half (because of penultimate candidate if higher than last; so we need to take not all $x_k$ - only with this condition) the total number of irregular ranks of length $k$; therefore, to the left of $Z$ can build $\frac{x_k}{2}$ ranks. To this was true for $k = 0$ and $k = 1$ (one rank in both cases), we assume $x_0 = x_1 = 2$.

Similarly, the right from the wrong $Z$ is a row of length $n - k$, but not arbitrary, and this, in which the second candidate above the first. Such ranks will be $\frac{x_{n-k}}{2}$.

It remains to note that $k$ candidates left by $Z$ can select $C_n^k$ means (and for each method is uniquely selected $n - k$ to the right of candidates $Z$). Thus, if $Z$ stands for $k$-th position, the number is still incorrect ranks

$$C_n^k \cdot \frac{x_k}{2} \cdot \frac{x_{n-k}}{2} = \frac{1}{4} C_n^k x_k x_{n-k}.$$

Summing over $k$, we find the number of ranks of irregular length $n + 1$:

$$x_{n+1} = \frac{1}{4} \sum_{k=0}^{n} C_n^k x_k x_{n-k} \quad (n = 1, 2, \ldots; x_0 = x_1 = 2).$$

So, for $n=6$, there will be incorrect lines:

$$\begin{aligned} x_6 &= \frac{1}{4} \sum_{k=0}^{5} C_5^k x_k x_{5-k} = \frac{1}{4} (2x_5 + 10x_4 + 10x_2 x_3 + 10x_3 x_2 + 10x_4 + 2x_5) = \\ &= \frac{1}{4} (4x_5 + 20x_4 + 20x_2 x_3) = x_5 + 5x_4 + 5x_2 x_3 \\ &\quad x_2 = \frac{1}{4} (4 + 4) = 2 \\ &\quad x_3 = \frac{1}{4} (2x_2 + 8 + 2x_2) = \frac{1}{4} (4 + 8 + 4) = 4 \end{aligned}$$ $$\begin{array}{l} x_{4} = \frac{1}{4} (x_{0} x_{3} + 3 x_{1} x_{2} + 3 x_{2} x_{1} + x_{3} x_{0}) = \frac{1}{4} (2 x_{0} x_{3} + 6 x_{1} x_{2}) = \\ = \frac{1}{4} (16 + 24) = \frac{40}{4} = 10 \\ \end{array}$$ $$\begin{array}{l} x_{5} = \frac{1}{4} (x_{0} x_{4} + 4 x_{1} x_{3} + 6 x_{2} x_{2} + 4 x_{3} x_{1} + x_{4} x_{0}) = \\ = \frac{1}{4} (2 x_{0} x_{4} + 8 x_{1} x_{3} + 6 x_{2}^{2}) = \frac{1}{4} (40 + 64 + 24) = \frac{128}{4} = 32 \\ x_{6} = x_{5} + 5 x_{4} + 5 x_{2} x_{3} = 32 + 50 + 40 = 122 \\ \end{array}$$

The lines, which are correct for us:

$$6! - x_{6} = 720 - 122 = 598.$$

Answer: 598.

http://www.AssignmentExpert.com