I Discovered The Fibonacci Numbers May 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…

l