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.

The answer I found was:
\begin{equation}
g(N) = N! - \sum_{i=0}^{N-1} \binom{N}{i} g(i)
\end{equation}
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.

It turns out that for me and my four siblings, we could go for 44 years without repeating in the way we are assigned to give gifts to each other. On my wife's side of the family, they could go for 265 years. Even so, this year we're starting a simple "wheel" to make assignments. A gives to B, B to C, C to D, D to E, and E to A. Next year we'll shift the assignments by one.

It's not exciting (to me, anyway) but it's simple and no one gives to the person giving to them (which apparently was a flaw in the previous years' assignments). This makes me think about directed graphs but I'm not going to go there today. For now I'm satisfied to know that my family could go most of a lifetime without repeating giving assignments for the group. Merry Christmas!