Counting number of rearrangements in which no person has the same right neighbor
How many permutations of $\{1, \ldots, n\}$ exist such that none of them contain $(i, i+1)$ (as a sequence) for $i \in {1,...,(n-1)}$?