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 such that for all ?
For that problem, the answer was . The number of permutations on items where no item moves more than one space from where it started is the -th Fibonacci number. Now, the obvious question is:
How many permutations are there in such that for and 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 . It’s easy enough for . There’s only one shuffle possible and it satisfies the constraint. For that matter, the same is (conventionally) true for . When you have zero items, there is only one (very Zen) way to shuffle them, and it certainly does not violate the constraints.
For , there are two shuffles. Both satisfy the constraints. Similarly, with , there are shuffles. All of them satisfy the constraints.
For , we get to the first interesting case. Here, some of the 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 shuffles have either the first element move to the back or the last element move to the front?
There are permutations that send the first element to the back. There are permutations that send the last element to the front. We might then think that there are 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 of those.
So, for , there are shuffles satisfying our constraint that .
What then of ? Well, it’s bedtime here. This is gonna have to wait.