Preselection Tests for the Full-time Training

Let $N_{n}$ be the number of permutations satisfying these conditions.

For $n=5$, the conditions are $s_{4}>s_{1}$ and $s_{5}>s_{2}, s_{1}$. Among the $5!$ permutations of $(1, \cdots, 5)$, half of them satisfy the condition $s_{4}>s_{1}$. Among these permutations, half of them satisfy also the condition $s_{5}>s_{2}$. Therefore, there are $30$ permutations satisfying both conditions $s_{4}>s_{1}$ and $s_{5}>s_{2}$.

To compute $N_{5}$, it is easier to subtract from $30$ the number of permutations which do not satisfy the condition $s_{5}>s_{1}$. These permutations satisfy the condition $s_{4}>s_{1}>s_{5}>s_{2}$ with no condition on $s_{3}$. Since there are $5$ possibilities for $s_{3}$, there are $5$ such permutations and
$$N_{5}=30-5=25$$
For $n=7$. There are more conditions and the method used for $n=5$ becomes complicated. That is why, we will use a different method based on an inductive relation for $N_{n}$.

For $n=1,2,3$ there are no conditions on the permutations. So
$$N_{1}=1!=1, \quad N_{2}=2!=2, \quad N_{3}=3!=6 .$$
For $n=4$, there is only one condition: $s_{4}>s_{1}$. This gives,
$$N_{4}=\frac{1}{2} 4!=12$$
For $n \geq 5$, we have the conditions $s_{n} \geq s_{1}, s_{2}, \ldots, s_{n-3}$. This means that at most there are only $s_{n-1}, s_{n-2}$ at most which can be greater than $s_{n}$. Therefore $s_{n} \in\{n, n-1, n-2\}$.

(a) When $s_{n}=n$, there are as many permutations as for $n-1$, that is $N_{n-1}$.

(b) When $s_{n}=n-1$, because of the conditions $s_{n} \geq s_{1}, s_{2}, \ldots, s_{n-3}$, we have $n \in\left\{s_{n-1}, s_{n-2}\right\}$.
- If $s_{n-1}=n$, there are as many permutations as for $n-2$, that is $N_{n-2}$.
- If $s_{n-2}=n$, because of the conditions $s_{n-1} \geq s_{1}, s_{2}, \ldots, s_{n-4}$ we have $s_{n-1} \in\{n-2, n-3\}$.
i. If $s_{n-1}=n-2$, there are as many permutations as for $n-3$, that is $N_{n-3}$.
ii. If $s_{n-1}=n-3$ then $s_{n-3}=n-2$ and there are as many permutations as for $n-4$, that is $N_{n-4}$.

(c) When $s_{n}=n-2$, because of the conditions $s_{n} \geq s_{1}, s_{2}, \ldots, s_{n-3}$, we have either $s_{n-1}=n, s_{n-2}=n-1$ or $s_{n-1}=n-1, s_{n-2}=n$. In each case there are as many permutations as for $n-3$, that is $N_{n-3}$.

Hence, we obtain the inductive relation
$$N_{n}=N_{n-1}+N_{n-2}+3 N_{n-3}+N_{n-4}$$
Therefore
$$\begin{gathered} N_{5}=12+6+3 \times 2+1=25 \\ N_{6}=25+12+3 \times 6+2=57 \\ N_{7}=57+25+3 \times 12+6=124 \end{gathered}$$