Now we're going to look at a classical combinatorial problem called the Birthday Problem that you've probably heard in one form of another, but we'll look at it in the context of analytic combinatorics. So, the idea is that you have a group of people, and one by one you ask each member of the group their birthday. And the question is how many people will you ask before you find two that have the same birthday? Well by the time you get to 365, then you'll have to get in the next one will have to have the same birthday as someone else. But usually it'll happen much earlier, so the question is what can we expect on average if, say, birthdays are random. So, a way to look at this as a ball and urn problem is just, we've got M urns, in this case it would be 365 urns. And we ask the birthday, and the person goes into the corresponding urn. And then, so each ball goes into a random urn. And then the question is how long until some urn gets two balls? So in this case, the sixth one is where we stop. So, if balls come into random urns, then the question is how long until some urn gets two balls. So let's look at how to analyze that using the symbolic method. So, to do that, we'll talk about a birthday sequence. So that's a word where no set has more than one element. So that is each [COUGH] each earn has either no elements or just one. And so, that's going to be the basis of the analysis. And the first question is how many different birthday sequences are there? So, again, so M is our parameter, that's the number of earns. We want to know the class of birthday sequences. And we'll have a generation function for that class. And, again, it's a string that has no duplicate letters, or it's a word where everybody's got either zero or 1 occurrence. So what's the construction for building birthday sequences? Well, it's pretty simple. We have M earns. We have a sequence of them, and every earn is either empty or has one element. That's directly construction for birthday sequences. So with the symbolic method, that translates immediately to the generating function for E goes to 1, z goes to z sequence of M of them just raises that to the Nth power. So, the EJF equation for birthday sequences is 1+zM. And then the counting sequence is a coefficient of N factorial in that. Sorry, N factorial times coefficient of zN in that, which is N factorial times M choose N. Which the M factorial's cancelled, so it's M factorial, over M minus N factorial, or the product of M(M-1), out to M-N + 1. That's the number of different birthday sequences. So with that, we can use to solve the birthday problem. So, with this logic, so we just showed that the number of in character words where no characters repeated is M factorial over M minus n factorial. So again, M's gotta be less than n in this, so that's the number. That's what we just showed. So that's, if we divide by M to the n, that's the probability that no character is repeated in a random M word of length n, it's the number that there were none repeated divided by the total number possible. Or another way to look at that is if we take them one at a time, that's the same as the probability that if we take a sequence of characters, or throw a sequence of balls in there, it's the same as the probability that the first time we get a repeat position, it's bigger than N. because the probability, the first N that there's no repeat, is exactly that. So it's the probability that the first repeat position is bigger than N. So now, if we just sum that, we get the expected position of the first repeat. Sum, and it only goes up to M because we're going to get a repeat by the time we get to M. So that's a familiar sum, that's the Q-function that we looked at in lecture four, and the result is square root of pi M over 2. Expected position of that first repeat is square root of pi M over 2. That's the analysis, completes the analysis of the birthday problem. So in our original problem, if we had and asked people their birthdays, and there is 365 days in a year, how many people do you have to ask before finding two with the same birthday. Well, you just have to compute square root of pi times 365 over two, and it's about 24. So, in a class of size 24, ask people one at a time. In a class of bigger than 24, you've got a Reasonable chance of finding the average number of people you have to ask before finding two with the same birthday is 24. There's an analysis in the book that talks about how many you have to ask to have a 50% chance that you have two with the same birthday. It's about in the same range level, although that's a different problem. So that's analytic combinatorics with words to take a look at the birthday problem.
