A Recurrence of Constrained Shuffles

A Recurrence of Constrained Shuffles June 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.

nklein software

software development and consulting