4. For any $n \in \mathbb{N}$, denote by $A_{n}$ the set of permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of set $\{1,2$, $\ldots, n\}$ satisfying

$$
k \mid 2\left(a_{1}+a_{2}+\cdots+a_{k}\right), \quad \text { for each } 1 \leq k \leq n
$$

Compute the number of elements of $A_{n}$.

(Vidan Govedarica)
4. Denote by $F_{n}$ the number of elements of $A_{n}$. Then $F_{1}=1, F_{2}=2, F_{3}=6$.

Consider any permutation $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ from $A_{n}, n>3$. Then $n-1$ must divide $2\left(a_{1}+\cdots+a_{n-1}\right)=n(n+1)-2 a_{n} \equiv 2-2 a_{n}(\bmod n-1)$, which implies that $a_{n}$ is equal to $1, \frac{n+1}{2}$ or $n$.

Suppose that $a_{n}=\frac{n-1}{2}$. Now $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)$, so $2 a_{n-1}-3$ is divisible by $n-2$ and hence must be equal to $n-2$, but then $a_{n-1}=\frac{n+1}{2}=a_{n}$, which is impossible.

If $a_{n}=n$ then $\left(a_{1}, \ldots, a_{n}\right) \rightarrow\left(a_{1}, \ldots, a_{n-1}\right)$ is a one-to-one correspondence with the elements of $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 of $\{1, \ldots, n-1\}$. It belongs to $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 $k=1, \ldots, n-1$. Again, this gives a one-to-one correspondence with the elements of $A_{n-1}$, so in this case there are also $F_{n-1}$ permutations.

This establishes the recurrence $F_{n}=2 F_{n-1}$ for $n>3$, which together with $F_{3}=6$ yields the formula $F_{n}=3 \cdot 2^{n-2}$ for $n \geq 3$.