Beautiful condition

Let $F(n)$ be the number of permutations of the set $\{1, 2, \ldots, n\}$ satisfying $1x_1\le2x_2\le3x_3\le\ldots\le nx_{n}\qquad(*)$ .

The key obversation needed to compute $F(n)$ is the following claim: “If a permutation satisfies $(*)$ , then either $x_{n-1}=n$ or $x_n=n$ ".

To prove the claim, assume, on the contrary, that $x_{n-k}=n$ for some $k>1$ . Then obverse that the set $\{x_{n-k+1}, \ldots, x_n\}$ must be a permutation of $\{n-k, n-k+1, \ldots, n-1\}$ , otherwise, there would have to be a number smaller than $n-k$ between them, which would violate $(*)$ . Now, which of the elements $x_{n-k+1}, \ldots, x_n$ is $n-k$ ? Obviously, it has to be the last one – otherwise $(*)$ would be violated too. Then the inequality $(*)$ gets the following form: $1x_1\le2x_2\le3x_3\le\ldots\le\underbrace{(n-k)x_{n-k}}_{n(n-k)}\le\ldots\le \underbrace{nx_{n}}_{n(n-k)}$ .

And therefore we actually have the equality after the position $n-k$ : $n(n-k)=(n-k)x_{n-k}=\ldots=nx_n$

But then it means that $n(n-k)$ is divisible by all the numbers $n-k+1, n-k+2, \ldots, n-1$ , which is not true. This contradiction concludes the proof of the claim.

The number of permutations satisfying $(*)$ and $x_n=n$ is $F(n-1)$ ; the number of permutations satisfying $(*)$ and $x_{n-1}=n$ is $F(n-2)$ .

Thus we get $F(1)=1, F(2)=2, F(n)=F(n-1)+F(n-2), n\ge3$ ,

which shows that $F(n)$ is the $(n+1)$ th Fibonacci number.

Thus $F(25)=\boxed{121393}$