We start with a simple question: what is the total number of permutations on $[k]=\{1,2,3,\dots, k\}$ such that $i$ is in position $i$ or $i+1$ for all $i<k$.
We have $k$ possibilities:
\begin{align*}
\begin{matrix}
1&2&3&\dots&k-2&k-1&k\\
1&2&3&\dots&k-2&k&k-1\\
1&2&3&\dots&k&k-2&k-1\\
1&2&3&\dots&k-3&k-2&k-1\\
&&&&\vdots\\
1&2&k&\dots&k-3&k-2&k-1\\
1&k&2&\dots&k-3&k-2&k-1\\
k&1&2&\dots&k-3&k-2&k-1\\
\end{matrix}
\end{align*}
A more general problem: What is the total number of permutations on $[k]=\{1,2,3,\dots,k\}$ such that $i$ is in position $p_i$ or $p_i+1$ for all $i<k$, where $p_i=p_j$ iff $i=j$.
This is identical to the previous question; there are $k$ possibilities, since we are, in essence, just changing the labeling of the numbers.
The general problem: Let $[n]=\{1,2,3,\dots,n\}$, and let $S\subseteq [n-1]$. What is the total number of permutations on $[n]$ such that for each $i\in S$, $i$ is in position $p_i$ or $p_i+1$, where $p_i=p_j$ iff $i=j$.
Let $\{s_1, s_2, \dots, s_k\}\subset S$, and without loss of generality, suppose $p_{s_i}<p_{s_j}$ for all $i<j$. We will call this subset maximal if it satisfies the following conditions:
- $p_{s_i}=p_{s_1}+i-1$
- If $s\in S\backslash \{s_1, s_2, \dots, s_k\}$, then $p_{s_1}\neq p_s+1$ and $p_s\neq p_{s_k}+1$
Since a maximal subset can be in $k$ of $k+1$ spots in a permutation of $[n]$, there are $k+1$ different possible ways for $\{s_1, s_2, \dots, s_k\}$ permute in $[n]$.
Therefore, we can partition $S$ into disjoint subsets: $S=S_1\cup S_2\cup\dots\cup S_r$, where each $S_i$ is maximal. So, the number of permutations on $[n]$ that satisfy our condition is
$$[(|S_1|+1)(|S_2|+1)\dots(|S_r|+1)]\cdot(n-|S|)!$$
The final factorial comes from the elements that were not in $S$ that are allowed to go anywhere.
Let's see this in action. For your second example, we have $n=4$, $S=\{1,2\}$, $p_1=1$ and $p_2=2$. Therefore, the only maximal subset of $S$ is $S$ itself. Hence, the number of permutations is
$$(|S|+1)\cdot(n-|S|)! = 3\cdot 2!=6.$$
As another example, suppose we were working with $\{1,2,3,4,5,6\}$, and we want
- $2$ to be in position $3$ or $4$,
- $4$ to be in position $4$ or $5$,
- $5$ to be in position $1$ or $2$.
We have $n=6$, $S=\{2,4,5\}$, $p_2=3$, $p_4=4$, and $p_5=1$. So the maximal subsets of $S$ are $S_1=\{2,4\}$ and $S_2=\{5\}$. Therefore, the number of permutations is
$$(|S_1|+1)(|S_2|+1)\cdot(n-|S|)! = 3\cdot2\cdot3!=36.$$
Best Answer
What you are looking for is known as derangement. However, for counting the number of derangement for say $n$-elements you could possible use a trick, compute$\frac{n!}{e}$ and then round off to an integer and this will give you the desired result.
This is actually another application of $e$, which was discovered by Jacob Bernoulli in the problem of derangement, also known as the hat check problem.