Tuesday, December 30, 2014

Number of New Pairs from N Old Pairs

I mentioned in my previous post how I had offered a \$5 cash prize to anyone who could solve a counting problem. This was offered to people who talked to me during a poster presentation on some research I had been working on. The problem was relevant to the research I was working on as a PhD student at the University of Utah.

Here I am standing in front of my poster. Nothing says "SCIENCE!" like a bow-tie and a white lab coat, right?



The problem is this:

A room is filled with people who are all at this moment shaking hands with someone else in the room (there are an even number of people), making N pairs of people. If everyone stops shaking hands with their current partner and then starts shaking hands with someone else, how many ways can we make N new pairs where no pair is the same as before?

To those who were offered this \$5 problem, I think they had to solve this for 6 pairs of people, if I remember right. Faculty had to solve for the general solution. It also had to be solved by midnight that night and submitted via email to qualify (about 8-10 hours).

This is not an easy problem (well, it wasn't for me). I don't remember how long it took me but it took quite a bit of head-scratching and took at least three or four pages of notes and simple examples in my notebook to come up with a general solution. That's why I felt confident that I wouldn't have to give the \$5 prize away, which I did not have to do. I probably should have offered more to pull more people into listening me talk about my research but as a student I felt enough risk offering just \$5.

First, let's solve the simpler problem. How many pairs can we make from $2N$ people in general? Answer: $N$. Oh, you wanted to know how many ways can we make $N$ pairs from $2N$ people? Sorry. (Many of you are probably not laughing at that. It sounded funnier in my head before I wrote it all out.)

The number of ways we can make $N$ pairs from $2N$ people (or things or whatever)
\begin{equation}
\frac{\prod_{i=1}^{N} \binom{2i}{2}}{N!}.
\end{equation}

We start $i$ equaling $1$ but it may make more sense to start from $N$ and work our way down to $1$ on that product. First we find $\binom{2N}{2}$, making our first pair of people from the $2N$ available to us. Then $\binom{2(N-1)}{2}$ to make the second pair from the $2(N-1)$ left and so on until we only have two left for $\binom{2}{2}$, which of course is just equal to one. So we could start $i$ at $2$ but I feel starting at $1$ is more instructive and complete. Then we divide by $N!$ because we don't care about the order of our $N$ pairs.

The answer for the \$5 problem in its general form is
\begin{equation}
g(N) = \frac{\prod_{i=1}^{N} \binom{2i}{2}}{N!} - \sum_{i=1}^{N} \binom{N}{i} g(N-i)
\end{equation}
where $g(0)=1$ and $n$ is the number of pairs. (This forms integer sequence A053871 from The Online Encyclopedia of Integer Sequences. That link gives some additional, interesting formulas for calculating the same sequence.)

The product you'll recognize as the equation for forming $N$ pairs from $2N$ people. But then it gets smaller, which you'd expect, by subtracting off a sum of $N$ terms. Let's talk about that sum.

The function $g(N)$ is the number of ways we can form $N$ new, unique pairs from $N$ old pairs. The number of ways we can do that is a subset of all the ways we can form $N$ pairs. The terms we are subtracting off are all of the ways we form $N$ pairs where $i$ pairs were the same as before and $N-i$ are new. There are $\binom{N}{i}$ ways to select $i$ old pairs and $g(N-i)$ ways to create $N-i$ new pairs. Subtract those terms away and we're left with all the ways we can make $N$ new pairs. It's recursively defined but using memory to store previously computed values would avoid long computations.

Seems simple enough. In my notebook I had to start from one pair and work my way up to, I think, four pairs to figure out the pattern. It was fun.

When I was looking through some old pictures I found this one of your's truly the day I did my dissertation defense:


My lab-mates wrote the "Good Try Job, Merrick!" message on the board while I was taking questions from my graduate committee without the public present. They were a pretty fun group. My lab-mates, that is. Unless you were on my graduate committee and are reading this right now. You were also fun. Oh, wait. You don't hold any power over me anymore. You were not fun. Your questions were hard and... Oh, sorry. I kinda forgot what I was talking about. Ah, the picture! There's my solution for $g(N)$! Fun!

And to my graduate committee, you may not have been fun but I was stretched and I passed. What more could I ask for?