# permutations of $1, 2, 3, \ldots, n$ in which each integer either occupies its natural position or is adjacent to its natural position

Let $p_n$ denote the number of permutations of $1, 2, 3, \ldots, n$ in which each integer either occupies its natural position or is adjacent to its natural position.
(a) Write a recurrence relation and initial conditions for $p_n$.
(b) Find an explicit formula for $p_n$.

I don't know how to approach this problem.. tbh can't fully understand the concept of this problem. Can anyone explain and go into details? or solve it?

• Welcome to MathSE. Please type your question rather than posting an image. Images cannot be searched. Reading this tutorial will help you learn how to typeset mathematics on this site. – N. F. Taussig Oct 27 '17 at 8:46

Interpreting the question

Suppose $n=4$. Then you can list all the ways to permute $1,2,3,4$. \begin{align} 1234\\ 1243\\ 1324\\ 1342\\ \vdots\\ 4312\\ 4321 \end{align}

Let us consider $1324$ as an example. "$1$" is the first digit, so it is in its "natural position." "$3$" is in the second digit, which is adjacent to its "natural position" (third digit). Similarly $2$ is adjacent to its natural position. Finally, $4$ is in its natural position since it is the fourth digit. Thus, this is one of the permutations counted in $p_4$.

If we consider $4312$, we note that $4$ is not in its natural position (fourth digit) or adjacent to it (third digit). Similarly $2$ is not in its natural position (second digit) or adjacent to it (first or third digits). So this would not be counted in $p_n$.

Hints for solving the problem

Initial conditions is not too hard. When $n$ is small like $n=1,2,3$, you can count them by hand.

To find a recurrence relation, suppose you have computed $p_1,\ldots,p_n$ already, and you want to compute $p_{n+1}$. Think about valid permutations of $1,\ldots,n+1$, and think about where $n+1$ must go. Can you use this to write $p_{n+1}$ in terms of $p_1,\ldots,p_n$?

• Thank you very much!! I will try when I get home!! If I understand correctly, you are suggesting the mathematical induction right? Thanks again!! – Guyong Kim Oct 27 '17 at 1:36