Solution: Rephrasing the problem's condition in a bit more abstract terms, We want to find the number of elements of the set \begin{align*} S= \{ \pi \mid \pi:\{ 1, \ . \ . ., 2016 \} \rightarrow \{ 1, \ . \ . \ ., 2016 \} \quad \text{a bijection, such that } \quad \pi ( i + 1) - \pi ( i) \leq 1 \quad \text{and} \quad \exists ! i,j \ : \pi ( i_0) = i_0 \neq j_0 = \pi ( j_0) \} \end{align*}Denote the problem's conditions by $ (\alpha_1) $ and $ (\alpha_2) $ respectively. Notice the following: \begin{align*} \pi ( i + 1) > \pi ( i) \quad \text{and } \quad (\alpha_1) & \Rightarrow \pi( i) + 1 \leq \pi( i + 1) \leq \pi ( i) + 1 \Rightarrow \pi ( i + 1) = \pi ( i) + 1 \\ & \\ \pi ( i + 1) < \pi ( i) & \Rightarrow \pi( i + 1) < \pi ( i) + 1 \Rightarrow \pi ( i + 1) \leq \pi ( i) + 1 \\ & \\ \pi ( i) < i & \Rightarrow \pi ( i + 1) \leq \pi ( i ) + 1 < i + 1 \Rightarrow \big( \pi (t) < t \big)\big( \forall t \geq i \big) \\ \end{align*}Now, because of the last deduction and since there exist only two $ i_0, j_0 $ such that $\pi(x) = x$, these two numbers must be successive integers. In other words, $ |i_0 - j_0| = 1 $. By symmetry, let $ j_0 = i_0 + 1 $. So, $ \pi ( i_0) = i_0 $ and $ \pi ( i_0 + 1) = i_0 + 1 $. Also, for all other $x \in \{ 1, . \ . \ ., 2016 \} - \{ i_0, j_0 \} \Rightarrow \pi ( x) \neq x $. Unless otherwise noted, in the following calculations $i = i_0$ and, therefore, $ i + 1 = i_0 + 1 = j_0 $. Now we need a lemma. Lemma: For all $ x \in \{ 1, \ . \ . \ ., i - 1 \} $, we have $ \pi ( x) > i + 1 $, and for all $ x \in \{ i + 2, \ . \ . \ ., 2016 \} $, we have $ \pi ( x) < i $. Proof: We consider the lemma's parts one by one. - Part 1: For all $ x \in \{ 1, \ . \ . \ ., i - 1 \} $, we have $ \pi ( x) > i + 1 $. For the sake of contradiction, assume the contrary: There exists some integer $ 1 \leq x \leq i - 1 $ such that $ \pi ( x) < i + 1 $. Since $ x \neq i $ we know that $ \pi ( x) \neq \pi ( i) = i $. Thus, $ \pi ( x) < i $. From $ (\alpha_2) $, we get $ \pi ( i) \leq \pi ( i - 1) + 1 \Rightarrow \pi ( i -1) \geq i - 1$. We also know that $ \pi ( i - 1) \neq i - 1 $, implying $ \pi ( i - 1) > i - 1 $. However, in order to attain the value $ \pi( i - 1) $ from $ \pi ( x) $, we would need all the steps(increases by one) from $ \pi ( x) $ to $ \pi ( i - 1) $. But this implies that there is some $ x \leq u \leq i - 1 $ with $ \pi ( u) = i $, contradicting the fact that $ \pi $ is a permutation and particularly that it is injective. - Part 2: For all $ x \in \{ i + 2, \ . \ . \ ., 2016 \} $, we have $ \pi ( x) < i $. Again, assume the contrary. This would mean that there exists some $ i + 2 \leq x \leq 2016 \ : \ \pi ( x) > i $. The condition $ (\alpha_2) $ implies \begin{align*} \pi ( i + 2) \leq \pi ( i + 1) + 1 & = i +2 \\ \text{ Since } \quad \pi ( i + 2) \neq i + 2, \ \pi( i) = i, \ \text{ and } \ \pi( i + 1) = i + 1 &\Rightarrow \pi ( i + 2) < i - 1 \\ \text{From } \quad \pi ( i + 2) < i + 2 &\Rightarrow \pi ( i + 2) < i - 1 \\ \text{using condition $ \alpha_1 $ we get } \quad \Rightarrow \pi ( i + 3) &\leq \pi ( i + 2) + 1 \\ & \leq i \\ \Rightarrow \pi ( i + 3) & \leq i - 1 \\ \ . & \\ \ . & \\ \ . & \\ \text{Inductively, } \quad \pi ( x) < i - 1 \quad \text{ for all $ x $ greater than $ i + 1 $ }\\ \end{align*}Contradicting our assumption. Thus, for all $ x \in \{ i + 2, \ . \ . \ ., 2016 \} $ we have $ \pi ( x) < i $, and the lemma is completely proved. $ \square $ Now, turning to our problem. From Part 1 of the Lemma, we know that there are at least $ i - 1$ integers greater than $ \pi( i + 1) = i + 1 $. Since there are exactly 2016 numbers, \begin{align*} i + 1 + i - 1 &\leq 2016 \\ 2i &\leq 2016 \\ \end{align*}Also, from the Part 2 of the Lemma, there are at least $ 2015 - i $ integers less than $ \pi ( i) = i $. Hence, \begin{align*} 2015 - i &\leq i \\ 2015 &\leq 2i \\ \end{align*}Last two deductions imply $2015 \leq 2i \leq 2016 $. Since $ i \in \mathbb{Z} $, we get $ i = \frac{2016}{2} $. Now, we need to make two crucial observations. Obesrvation 1: The number of possible permutations $ \pi $ (under the problem's conditions) is exactly the product of the number of permutations of $( i + 2, \ . \ . \ ., 2016)$ and the number of permutations of $( 1, \ . \ . \ ., i - 1)$, where the condition $(\alpha_1)$ holds. Also, these two mentioned numbers are equal to each other. Define $ s_1, \ . \ . \ .,s_t $ as the longest- possible monotonically-increasing subsequences of $ \pi $. . . * * - For example the permutation $ \pi (1,2,3,4,5,6,7,8) = (7,8,6,4,5,1,2,3)$ has the subsequences $s_1=(7,8), \quad s_2 = (6), \quad s_3 = (4, 5), \quad s_4 = (1,2,3) $. Observation 2: The number of configurations of $ (s_1, \ . \ . \ . , s_t) $ is the same as the number of permutations of $( 1, \ . \ . \ ., i - 1)$. The reason behind this is that to every permutation of $( 1, \ . \ . \ ., i - 1)$ we can assign a unique tuple that represents the monotone subsequences starting from the $\pi ( 1) $. Also, for every tuple $ (s_1, \ . \ . \ . , s_t) $ with $ 1 \leq | s_1|, \ . \ . \ ., | s_{ t}| \leq \frac{ 2016}{ 2} - 1 $ and $ | s_1| + . \ . \ . \ + | s_{ t}| = \frac{ 2016}{ 2} - 1 $, we can assign a unique permutation $ ( 1, \ . \ . \ ., \frac{ 2016}{ 2} - 1) $. that has the first $ s_1 $ elements $ \big(\pi ( 1), \ . \ . \ ., \pi (|s_1|)\big) = \big(2017 - s_1, \ . \ . \ ., 2017 - 1 \big) $, the next $ s_2 $ elements $ \big(\pi ( |s_1| + 1), \ . \ . \ ., \pi (|s_1| + |s_2|)\big) = \big( 2017 - s_1 - s_2, \ . \ . \ ., 2017 - s_1 - 1 \big) $ and so on. It is a well-known result that for a specified $t$ the number of positive-integer tuples $(s_1,...,s_t)$ for which $s_1+...+s_t = k $ is exactly $\binom{k - 1}{t - 1}$. But we are going to include the proof at the end. Since our number of subsequences can vary freely on $ \{ 1, \ . \ . \ ., \frac{2014}{2} \} $, we get the sum \begin{align*} \sum_{ t = 1}^{ \frac{ 2014}{ 2}} \binom{ \frac{ 2014}{ 2} - 1}{ t - 1} =\sum_{ t = 0}^{ \frac{ 2012}{ 2}} \binom{ \frac{ 2012}{ 2}}{ t} = 2^{ \frac{ 2012}{ 2}} \end{align*}As we have mentioned earlier on observation 1, the required result is the square of this number. So, the required number(the number of elements of $ S $) is $ |S| = 2^{2012} $ $ \blacksquare $. Below you may find the proof of the statement that we have used. Statement: For a specified $t$, the number of positive-integer tuples $(s_1,...,s_t)$ for which $ s_1+ \ . \ . \ . \ + s_t = k $ is exactly $\binom{ k - 1}{ t - 1}$. Proof: Suppose that one has $ k $ objects to be placed into $ t $ bins such that all bins contain at least one object; one distinguishes the bins (say they are numbered $ 1 $ to $ t $) but one does not wish to distinguish the $ k $ stars (so configurations are only distinguished by the number of stars present in each bin; in fact a configuration is represented by a $ t $-tuple of positive integers). Thus one views the $ k $ stars as fixed objects defining $ k - 1 $ gaps, in each of which there may or not be one bar (bin partition). One has to choose $t - 1$ of them to actually contain a bar; therefore there are $ \binom{ k - 1}{ t - 1} $ possible configurations. Comment: The same proof holds for any $ m \in \mathbb{N} $ and not only for $ m = 2016 $.