Counting on Your Fingers
Warning: the title suggests that the mathematics ahead will be simple. That is not true.
Earlier today my friend Alex posed a question. How many ways are there to put the fingers (and thumbs which will be called fingers from now on) of both hands together so that no finger is matched with the equivalent finger on the other hand. We played around for a bit, trying to come up with a recursive formula, but it got surprisingly messy.
A good way into these sort of problems is to start with smaller cases and try to find a pattern. With 1 finger, there are no ways to match them. With 2 fingers 1 out of the 2 ways to pair your fingers obeys our criteria and by the time you get to the 3 case, we have to do a bit more work:
Notice the last cross that was originally a tick. That set us back. Sorry Alex.
Here's a table showing the first few results:
| Fingers (n) | Correct ways | Incorrect ways | Total ways (n!) |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 2 | 1 | 1 | 2 |
| 3 | 2 | 4 | 6 |
| 4 | 9 | 15 | 24 |
| 5 | 44 | 76 | 120 |
On the far right we have just the total number of ways to pair the fingers with no restrictions. This is easy to work out; for instance in the 5 case, the first finger can be paired with any other finger (5 possibilities). The next finger only has 4 possible choices left, the next has 3 and so on. Overall we get 5x4x3x2x1=120.
What we are looking for is a recursive formula so that if we know the number of ways for lower numbers of fingers, then we can pop it into an equation to work out the number of ways for an extra finger.
Here's the logic. Let's say that finger number 1 on the left hand is paired up with finger number x on the right hand. x can't be 1, because that would be against the requirement. The crucial question is: which finger does finger x on the left hand pair with?
There are two cases. If it pairs with 1 on the right hand, then you have successfully reduced the problem to the same position but with two pairs of fingers removed. Thus, it is just the n-2 case.
If not, then you have exactly n-1 fingers, each of which is forbidden to pair with exactly one other finger (for x's case, their forbidden pairing is with 1). This is the n-1 case.
So our recursive formula becomes: un=(n-1)(un-1+un-2)
It turns out that this is a famous formula and this area of mathematics is called dearrangement.
I want to present you with one of the surprising results in this field. (Without proof but if you want to go deeper into understanding why then this will get you thinking in the right way. Proceed with caution.) Here is a closed form version of the formula:
It just looks so unlikely. The bracket like symbols are the floor function. They take the result of whatever is inside them and then round it down to the next integer. The +1/2 is just there to bodge the result up to the next integer for even n, and let it remain as the lower integer for odd n. The surprising thing here is that the ratio of n! to e is the answer we want to the nearest integer.
Put another way, the ratio of the number of ways of touching your fingers together, to the number of ways to touch them together so that they don't match to their equivalent digit as the number of fingers tends to infinity, tends to e. It's hard not to smile when you get a surprising result from a different area of mathematics.
