Combinatorics for Kittens Part 2 The Birthday problem Ok. You've probably heard of this one, but let's take it from the top. There are 365 days in the year. So how come, even in a smallish group, there's always a couple of people who share a birthday? Freaky psychic powers, say some - similar souls seeking each other out. Let's look at it this way. Consider a pile of cats. And three hundred and sixty five boxes. These are big boxes though - each one ould hold many cats. And cats do like to play in boxes. How many ways can they play? Cat 1 can choose any of the 365 boxes. Cat 2 can choose any of the 365 boxes. And so on. So there are 365^n ways to arrange those cats. But some of them - there are multiple cats in a single box. We don't think that's likely. So let's count how many ways we can arrange them WITHOUT overlap. Well, that's easy - from the previous page we know it's 365Cn - 365 boxes and fill up n of them. Obviously if we've more than 365 cats, it's zero. Note that it's nCm and not nPm because we don't care WHO shares a birthday in the group. So there are 365^n ways of arranging them, and 365Cn 'good' ways, that is ways that do not share a birthday, of arranging them. So what are the chances of getting a 'good' arrangement? g(n) = 365^n / 365Cn At this point you either get a calculator with a reallllly wide screen, or cheat a bit. You can do some cancellations, or use Stirlings approximation. (Which says that n! is roughly equal to n^n * e^-n * ( 2 * pi * n )^1/2 ) And an interesting thing happens when you graph it: (Image68.gif) Around about 23-25 it becomes more likely that you DO have more than one kitten in a box (or person sharing a birthday) than you don't.