# In how many ways can string $123456$ be rearranged if at least one character needs to move more than one place from its original position?

In how many ways can string $S=123456$ be rearranged if at least one character needs to move more than one place from its original position?

For example, string $12534$ satisfies the condition because in the original string $12345$ the position of five is $5$ (using one-based index) while in $12534$ the position of five is $3$ and $5-3>1$.

I thought to find first the number of strings where numbers can be moved at most one position to the left or to the right. This is the recurrence I have: $$a_n=a_{n-1}+a_{n-2}$$ Now there're $6!$ possible permutations of $S$ so the number of possible ways that at least one digit moves more than one place from its original position is $6!-a_6=720-13=707$.

I feel like I'm missing some inclusion/exclusion logic here.

• Your solution looks fine. – Jaroslaw Matlak Jun 12 '18 at 13:18
• I can verify that this is correct. Inclusion/exclusion is more useful if the problem were to count strings where all characters must move more than 1 place from their original position. – N. Shales Jun 13 '18 at 10:01

As already discussed in the comments, your approach and your recurrence are correct and you don't need inclusion–exclusion here. In a string of length $$n$$ with no number moved by more than one position, the $$n$$ has to be either in position $$n$$ or in position $$n-1$$. In the former case, the remaining $$n-1$$ numbers can form any admissible string of length $$n-1$$. In the latter case, the only number that's allowed to move to position $$n$$ is $$n-1$$, so $$n-1$$ and $$n$$ swap places, and the remaining $$n-2$$ numbers can form any admissible string of length $$n-2$$. Thus $$a_n=a_{n-1}+a_{n-2}$$. Since $$a_0=a_1=1$$, this yields the Fibonacci numbers.