Rearranging a set with limitations on how far each element can move

Question

Suppose we have a set of elements, which we want to rearrange. However, no elements can be moved more than 1 slot away from its original position (items can also be kept in the same position).

For instance, with a 3-element set, $ABC$, there are 3 such arrangements: $ABC$, $BAC$, $ACB$. With a 4 element set, $ABCD$, there are 5 arrangements: $ABCD$, $ABDC$, $ACBD$, $BACD$, $BADC$.

Let $M(n,1)$ be the number of ways to rearrange a set with $n$ elements such that each element can only be moved 1 slot.

Each reordering can either start with $A$... (remaining n-1 elements) or $BA$... (remaining n-2 elements). Hence:

$M(n,1)$ = $M(n-1,1)$ + $M(n-2,1)$

That is, the Fibonacci sequence.

The situation becomes much more complex when we consider $M(n,2)$; that is, each element can be moved up to 2 slots. We can easily calculate the first few terms:

$M(2,2)$ = 2

$M(3,2)$ = 6

$M(4,2)$ = 14

$M(5,2)$ is harder to calculate, but I think it is 32. It is hard to count the number of ways systematically, though. Any ideas of how to go about the problem? Is there any way to find a general formula for $M(n,x)$?

Answer 1

I think I've managed to crack the case for $M(n,2)$.

For notational simplicity, let $M(n,2)$ = $F(n)$. We now need to introduce a new function, $G(n)$, defined as the same as $F(n)$ except that, while all other elements of the set may move up to 2 slots either direction, the first element may only move one slot.

Again, we go for a recursive approach. The first element of the sequence can be either $A, B$ or $C$.

• If it starts with $A$, there are $F(n-1)$ ways to rearrange the remaining elements.
• If it starts with $B$, there are $G(n-1)$ ways, as all other elements face the same constraints, but now the $A$ has only 2 positions it can go in.
• If the sequence starts with $C$, we must further consider three cases: it can start either $CA$, $CB$ or $CD$. Starting $CA$ is analogous to $G(n-2)$, as all remaining elements face the same constraints except the $B$ has only 2 positions it can go in. Starting $CB$ forces the $A$ to go next, leaving $F(n-3)$ ways to rearrange the remaining elements, while similarly starting $CD$ forces the next terms of the sequence to be $AB$, leaving $F(n-4)$ ways.

This reasoning is represented in the tree diagram below. All said and done, we find that:

$F(n) = F(n-1) + F(n-3) + F(n-4) + G(n-1) + G(n-2)$

Now we must unpack $G(n)$. Using a similar process, we observe that the set can start in one of three ways: $A, BA$ or $CA$. This corresponds to the equation:

$G(n) = F(n-1)+F(n-2)+G(n-2)$

Since $G(n-2) = F(n-3) + F(n-4) + G(n-4)$, we can expand the equation to yield:

$G(n) = F(n-1)+F(n-2)+F(n-3)+F(n-4)+...$

Now we can use this equation to expand the earlier equation for $F(n)$.

$F(n) = F(n-1)+F(n-2)+3F(n-3)+3F(n-4)+2F(n-5)+2F(n-6)+2F(n-7)...$

That is, the coefficients of this unending equation go 1,1,3,3,2,2,2,2.... Thankfully, this can be simplified with a nifty trick: simply add $F(n-1)$ to the right hand side while subtracting its expansion. This leaves us with:

$F(n)=2F(n-1)+2F(n-3)-F(n-5)$

This allows us to easily compute the series $M(n,2)$: 1,2,6,14,31,73,172...