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,N_2=2!=2,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\ge 5$, we have the conditions $s_n\ge s_1,s_2,\dots ,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\ge s_1,s_2,\dots ,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}\ge s_1,s_2,\dots ,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\ge s_1,s_2,\dots ,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}+3N_{n-3}+N_{n-4}$$ Therefore $$\begin{array}{c}{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{array}$$