I Discovered The Fibonacci Numbers

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)$ .