Friday, November 6, 2015

Counting for Christmas!

So my four siblings and I are all adults. We decided several years ago that instead of everyone trying to get a present for everyone else, we would instead each give to only one sibling. We felt this was especially necessary as some of us began to have spouses and kids. We do the same thing on my wife's side of the family. She has five siblings. (We both come from pretty stereotypically sized Mormon families.) This year I was thinking more about this and I wanted to how many different ways could we be assigned to give to each other.

This is a little more complicated than just finding the number of permutations, or $N!$. This is because no one wants to be assigned to give a gift to themselves, which many of the permutations would end up doing. What we want is the subset of permutations where each item's position is different than one particular permutation. For simplicity this permutation, for $N=5$, would be A,B,C,D,E. So A can't be in the first spot, nor B in the second, and so on. But of all of the $N!$ permutations, you could choose any one and then build the rest around that one. But the final number will be the same.

where $g(0)=1$, though I'm not sure that's necessary to say, explicitly. This forms the integer sequence A000166 from the Online Encyclopedia of Integer Sequences. This is somewhat similar to the one I described in my post about finding the number of new pairs from $N$ already-formed pairs in that it uses a sum of products of a binomial coefficient with a previously calculated answer (i.e. it's recursively defined).
Even though it's similar to what I described in my previous post, let's talk about this again. First take all $N!$ permutations. Now we make that number smaller by subtraction. We would expect this. The key part is that product. Consider again the permutation A,B,C,D,E. Let's choose two of them to stay right where they are. A and B, for example. They are in their original positions. We're left with three, C, D, and E, that are not in their original positions. The number of ways that's possible is found using $g(3)$. Do this for all of the ways you can choose two of the letters (there's that binomial coefficient). Then I say "and so on" and *poof* out comes the equation.