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.

I Discovered The Fibonacci NumbersMay 31st, 2009 Patrick Stein

Alright, I wasn’t the first. But, I wasn’t particularly expecting to find them either.

One nascent game concept that I have in my head requires me to do some constrained shuffling. As an example constraint, imagine that you need to shuffle a deck of cards while ensuring that no card moved more than five spots away from where it started. Or, imagine that you had to shuffle the deck so that a card of rank $r$ could only move to spot that had been held by a card of rank $r-1$, $r$, or $r+1$.

In the general case, you have a directed graph with vertexes $\left\{ v_1, v_2, v_3, \ldots, v_n \right\}$ and a permutation $\pi$ such that $\pi(i)$ can only equal $j$ if there is an edge in the graph from $v_i$ to $v_j$.

Well, as this is for a game, it would get pretty boring if there were only a few possible shuffles. On the other hand, if there are a large number of possible shuffles, then I haven’t really restricted the shuffling at all for all practical purposes. So, then the question is: for a given directed graph, how many possible shuffles are there? Can I generate them without generating any of the invalid permutations, too?

Today, I started with the How many?-question. I started with a very simple graph. The vertexes are spaced evenly along an east-west line. Each vertex is connected only to itself, its nearest neighbor to the east, and its nearest neighbor to the west. Put another way, $\left| \pi(i) - i \right| \le 1$ for $i \in [1,n]$.

Let’s say we already had a row of $n-1$ vertexes. If we add another vertex at the beginning of the row, then there are two things that a shuffle can do to that new vertex: leave it where it is or swap it with what had been the first vertex in the row. Now, suppose that $c(n)$ is the count of valid shuffles for $n$ vertexes in this configuration. The case where our new vertex stays where it is leaves $c(n-1)$ possibilities for the rest of the row. The case where our new vertex swaps places with the old first vertex leaves $c(n-2)$ possibilities. As such, $c(n) = c(n-1) + c(n-2)$.

Cha-ching. Note that $c(1) = 1$ and $c(2) = 2$, then $c(n) = F_{n+1}$ where $F_i$ are the Fibonacci numbers.

Things get a great deal messier if we move up to $\left| \pi(i) - i \right| \le 2$. More on that some other time…