, 2020

Denote by $P_{n}$ the number of permutations that satisfy (*). It is easy to see that $P_{1}=1$ and $P_{2}=2$.

Lemma 1. Let $n \geqslant 3$. If a permutation $a_{1}, \ldots, a_{n}$ satisfies (*) then either $a_{n}=n$, or $a_{n-1}=n$ and $a_{n}=n-1$.

Proof. Let $k$ be the index for which $a_{k}=n$. If $k=n$ then we are done.
If $k=n-1$ then, by $(*)$, we have $n(n-1)=(n-1) a_{n-1} \leqslant n a_{n}$, so $a_{n} \geqslant n-1$. Since $a_{n} \neq a_{n-1}=n$, the only choice for $a_{n}$ is $a_{n}=n-1$.
Now suppose that $k \leqslant n-2$. For every $k<i<n$ we have $k n=k a_{k} \leqslant i a_{i}<n a_{i}$, so $a_{i} \geqslant k+1$. Moreover, $n a_{n} \geqslant(n-1) a_{n-1} \geqslant(n-1)(k+1)=n k+(n-1-k)>n k$, so $a_{n} \geqslant k+1$. Now the $n-k+1$ numbers $a_{k}, a_{k+1}, \ldots, a_{n}$ are all greater than $k$; but there are only $n-k$ such values; this is not possible.
If $a_{n}=n$ then $a_{1}, a_{2}, \ldots, a_{n-1}$ must be a permutation of the numbers $1, \ldots, n-1$ satisfying $a_{1} \leqslant 2 a_{2} \leqslant \ldots \leqslant(n-1) a_{n-1}$; there are $P_{n-1}$ such permutations. The last inequality in (*), $(n-1) a_{n-1} \leqslant n a_{n}=n^{2}$, holds true automatically.
If $(a_{n-1}, a_{n})=(n, n-1)$, then $a_{1}, \ldots, a_{n-2}$ must be a permutation of $1, \ldots, n-2$ satisfying $a_{1} \leqslant \ldots \leqslant(n-2) a_{n-2}$; there are $P_{n-2}$ such permutations. The last two inequalities in (*) hold true automatically by $(n-2) a_{n-2} \leqslant(n-2)^{2}<n(n-1)=(n-1) a_{n-1}=n a_{n}$.
Hence, the sequence ( $P_{1}, P_{2}, \ldots$ ) satisfies the recurrence relation $P_{n}=P_{n-1}+P_{n-2}$ for $n \geqslant 3$. The first two elements are $P_{1}=F_{2}$ and $P_{2}=F_{3}$, so by a trivial induction we have $P_{n}=F_{n+1}$.

We claim that all sought permutations are of the following kind. Split $\{1,2, \ldots, n\}$ into singletons and pairs of adjacent numbers. In each pair, swap the two numbers and keep the singletons unchanged.
Such permutations correspond to tilings of a $1 \times n$ chessboard using dominoes and unit squares; it is well-known that the number of such tilings is the Fibonacci number $F_{n+1}$.
The claim follows by induction from

Lemma 2. Assume that $a_{1}, \ldots, a_{n}$ is a permutation satisfying (*), and $k$ is an integer such that $1 \leqslant k \leqslant n$ and $\{a_{1}, a_{2}, \ldots, a_{k-1}\}=\{1,2, \ldots, k-1\}$. (If $k=1$, the condition is empty.) Then either $a_{k}=k$, or $a_{k}=k+1$ and $a_{k+1}=k$.

Proof. Choose $t$ with $a_{t}=k$. Since $k \notin\{a_{1}, \ldots, a_{k-1}\}$, we have either $t=k$ or $t>k$. If $t=k$ then we are done, so assume $t>k$.
Notice that one of the numbers among the $t-k$ numbers $a_{k}, a_{k+1}, \ldots, a_{t-1}$ is at least $t$, because there are only $t-k-1$ values between $k$ and $t$. Let $i$ be an index with $k \leqslant i<t$ and $a_{i} \geqslant t$; then $k t=t a_{t} \geqslant i a_{i} \geqslant i t \geqslant k t$, so that all the inequalities turn into equalities, hence $i=k$ and $a_{k}=t$. If $t=k+1$, we are done.
Suppose that $t>k+1$. Then the chain of inequalities $k t=k a_{k} \leqslant \ldots \leqslant t a_{t}=k t$ should also turn into a chain of equalities. From this point we can find contradictions in several ways; for example by pointing to $a_{t-1}=\frac{k t}{t-1}=k+\frac{k}{t-1}$ which cannot be an integer, or considering
the product of the numbers $(k+1) a_{k+1}, \ldots,(t-1) a_{t-1}$; the numbers $a_{k+1}, \ldots, a_{t-1}$ are distinct and greater than $k$, so
$$(k t)^{t-k-1}=(k+1) a_{k+1} \cdot(k+2) a_{k+2} \cdot \ldots \cdot(t-1) a_{t-1} \geqslant((k+1)(k+2) \cdot \ldots \cdot(t-1))^{2} .$$
Notice that $(k+i)(t-i)=k t+i(t-k-i)>k t$ for $1 \leqslant i<t-k$. This leads to the contradiction
$$(k t)^{t-k-1} \geqslant((k+1)(k+2) \cdot \ldots \cdot(t-1))^{2}=\prod_{i=1}^{t-k-1}(k+i)(t-i)>(k t)^{t-k-1}$$
Therefore, the case $t>k+1$ is not possible.