Number of ways of visiting N places

Considering that the sequence in which he visits these $n$ cities, is $$a_1, a_2, \dots, a_n$$ then $a_i \neq i$. This is a derangement, whose formula is given by $$!n=\left[\frac{n!}{e}\right]$$ where $[x]$ is the nearest integer function and $!n$ is the number of derangements for an sequence with $n$ elements.

This sequence also appears in the Online Encyclopedia of Integer Sequences, which also provides you with recurrence relations, namely $$!n=(n-1)[!(n-1)+!(n-2)]$$for the number of derangements.

Hint look up dearrangements. $D_n=N!(1-1\frac{1}{2!}...+\frac{(-1)^n}{n!})$