2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your solution looks fine. $\endgroup$ – Jaroslaw Matlak Jun 12 '18 at 13:18
  • 1
    $\begingroup$ 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. $\endgroup$ – N. Shales Jun 13 '18 at 10:01
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.