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?

Thank you in advance.

  • $\begingroup$ 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. $\endgroup$ – 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$?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.