4. Let $n \in \mathbb{N}$ and $A_{n}$ be the set of all permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of the set $\{1,2, \ldots, n\}$ such that

$$
k \mid 2\left(a_{1}+a_{2}+\cdots+a_{k}\right) \quad \text { for every } 1 \leqslant k \leqslant n
$$

Determine the number of elements in the set $A_{n}$.

(Vidan Govedarija)
4. Let $F_{n}$ denote the number of elements in the set $A_{n}$. We have $F_{1}=1, F_{2}=2$ and $F_{3}=6$. For $n>3$, consider any permutation $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ in $A_{n}$. Since $n-1$ divides $2\left(a_{1}+\cdots+a_{n-1}\right)=n(n+1)-2 a_{n} \equiv 2-2 a_{n}(\bmod n-1)$, it follows that $a_{n}$ is equal to $1, \frac{n+1}{2}$ or $n$.

Assume that $a_{n}=\frac{n+1}{2}$. Then $n-2$ divides $2\left(a_{1}+\cdots+a_{n-2}\right)=n^{2}-$ $1-2 a_{n-1} \equiv 3-2 a_{n-1}(\bmod n-2)$. Therefore, it must be that $2 a_{n-1}-3=n-2$, but then $a_{n-1}=\frac{n+1}{2}=a_{n}$, a contradiction.

If $a_{n}=n$, then $\left(a_{1}, \ldots, a_{n}\right) \rightarrow\left(a_{1}, \ldots, a_{n-1}\right)$ is a bijective mapping to the set $A_{n-1}$, so there are $F_{n-1}$ such permutations.

If $a_{n}=1$, then $\left(a_{1}-1, \ldots, a_{n-1}-1\right)$ is a permutation on $\{1, \ldots, n-1\}$ that belongs to the set $A_{n-1}$ because $2\left(\left(a_{1}-1\right)+\cdots+\left(a_{k}-1\right)\right)=2\left(a_{1}+\cdots+a_{k}\right)-2 k$ is divisible by $k$ for $1 \leqslant k \leqslant n-1$. As in the previous case, there are $F_{n-1}$ such permutations.

We conclude that $F_{n}=2 F_{n-1}$ for $n>3$, which together with $F_{3}=6$ gives $F_{n}=$ $3 \cdot 2^{n-2}$ for $n \geqslant 3$.