## A Recurrence of Constrained ShufflesJune 2nd, 2009 Patrick Stein

Earlier, I posted about finding the Fibonacci numbers when counting a very simple constrained shuffle. In that article, I was concerned with the question: How many permutations are there in $\Sigma_n$ such that $\left| \pi(i) - i \right| \le 1$ for all $i \in [1,n]$?

For that problem, the answer was $F_{n+1}$. The number of permutations on $n$ items where no item moves more than one space from where it started is the $(n+1)$-th Fibonacci number. Now, the obvious question is: How many permutations are there in $\Sigma_n$ such that $\left| \pi(i) - i \right| \le k$ for $i \in [1,n]$ and $k$ is an arbitrary positive integer?

### Let’s not start so arbitrary just yet though…

Let’s just look for a moment at how much trickier things become when we let $k = 2$. It’s easy enough for $n = 1$. There’s only one shuffle possible and it satisfies the constraint. For that matter, the same is (conventionally) true for $n = 0$. When you have zero items, there is only one (very Zen) way to shuffle them, and it certainly does not violate the constraints.

For $n = 2$, there are two shuffles. Both satisfy the constraints. Similarly, with $n = 3$, there are $3! = 6$ shuffles. All of them satisfy the constraints.

For $n = 4$, we get to the first interesting case. Here, some of the $4! = 24$ shuffles violate the constraints. So, how many shuffles are still possible? To tackle this, we are going to use an inclusion-exclusion counting. The only items that could be out of place are the first and the last. So, how many of the $4!$ shuffles have either the first element move to the back or the last element move to the front?

There are $3!$ permutations that send the first element to the back. There are $3!$ permutations that send the last element to the front. We might then think that there are $4! - 2\cdot 3!$ valid shuffles. Alas, there are some shuffles that move both the first element to the back and the last element to the front. We have counted those twice. There are $2! = 2$ of those.

So, for $n = 4$, there are $4! - 2\cdot 3! + 2! = 24 - 12 + 2 = 14$ shuffles satisfying our constraint that $\left| \pi(i) - i \right| \le 2$.

What then of $n = 5$? Well, it’s bedtime here. This is gonna have to wait.

Goodnight.