1 00:00:00,012 --> 00:00:05,160 Now we're going to look at a classical combinatorial problem called the birthday 2 00:00:05,160 --> 00:00:10,542 problem that you've probably heard in one form or another but we'll look at it in 3 00:00:10,542 --> 00:00:16,488 the context of analytic combinatorics. So the idea is that you have a group of 4 00:00:16,488 --> 00:00:21,695 people and one by one you ask each member of the group their birthday. 5 00:00:21,695 --> 00:00:28,335 And the question is, how many people should you ask, will you ask before you 6 00:00:28,335 --> 00:00:34,375 find two that have the same birthday. Well by the time you get to 365, then 7 00:00:34,375 --> 00:00:40,102 you'll after you get, you know the next one will have to have the same birthday as 8 00:00:40,102 --> 00:00:43,565 someone else. But usually it will happen much earlier. 9 00:00:43,565 --> 00:00:48,449 So, the question is what can we expect on average if say the birthdays are random. 10 00:00:48,449 --> 00:00:53,190 So a way to look at this is a ball and urn problem. 11 00:00:53,190 --> 00:00:58,755 It's just, we've got m urns, so in this case it would be 365 urns. 12 00:00:58,755 --> 00:01:04,351 And we ask the birthday and the person goes to the corresponding urn. 13 00:01:04,351 --> 00:01:08,245 And then so each ball goes into a random urn. 14 00:01:08,245 --> 00:01:13,750 And then the question is how long until some urn gets two balls. 15 00:01:13,750 --> 00:01:18,112 So, in this case the 6th one that's where we stop. 16 00:01:18,113 --> 00:01:24,852 So if the balls come at random urns then the question is how long until some urn 17 00:01:24,852 --> 00:01:29,012 gets 2 balls. So, let's look at how to analyze that 18 00:01:29,012 --> 00:01:34,989 using the symbolic method. So to do that we''ll talk about a birthday 19 00:01:34,989 --> 00:01:38,981 sequence. So that's a word where no set has more 20 00:01:38,981 --> 00:01:45,198 than one element. So that is each, each urn has either no 21 00:01:45,198 --> 00:01:50,405 elements or just 1. And so that's going to be the basis of, of 22 00:01:50,405 --> 00:01:54,114 the analysis. And the first question is how many 23 00:01:54,114 --> 00:01:59,840 different birthday sequences are there? So, again if, so m is our parameter. 24 00:01:59,840 --> 00:02:05,090 That's the number of urns. We want to know the, class of birthday 25 00:02:05,090 --> 00:02:10,223 sequences and we'll have a generating function, for that class. 26 00:02:10,224 --> 00:02:15,924 And again, it's a string that has no duplicate letters or it's a word where 27 00:02:15,925 --> 00:02:22,324 everybody's got either 0 or 1 occurrence. So, what's the construction for building 28 00:02:22,324 --> 00:02:26,241 birthday sequences? Well, it's pretty simple. 29 00:02:26,241 --> 00:02:29,416 We have m urns. We have a sequence of them. 30 00:02:29,416 --> 00:02:32,986 And every urn is either empty, or has one element. 31 00:02:32,986 --> 00:02:39,191 That's the directly construction for birthday sequences. 32 00:02:39,191 --> 00:02:45,568 So, with the symbolic method that translates immediately to the generating 33 00:02:45,568 --> 00:02:51,904 function for e goes to 1, e goes to z, sequence of m of them just raise it up to 34 00:02:51,904 --> 00:02:57,737 the mth power. So the EGF equation for birthday sequences 35 00:02:57,737 --> 00:03:04,964 is 1 plus z to the n and then the counting sequence is coefficient of n factorial in 36 00:03:04,964 --> 00:03:10,832 that, so it, sorry, n factorial times coefficient of z to the n in that. 37 00:03:10,832 --> 00:03:16,594 Which is n factorial times m choose n which, the n factorial cancels so it's m 38 00:03:16,594 --> 00:03:22,075 factorial or m minus n factorial or the product of m, m minus 1 down to m minus n 39 00:03:22,075 --> 00:03:25,493 plus 1. That's the number of different birthday 40 00:03:25,493 --> 00:03:32,385 sequences. So with that we can use to, to solve the 41 00:03:32,386 --> 00:03:41,201 birthday problem so with this logic. So we just showed that the number of n 42 00:03:41,201 --> 00:03:49,769 character words where no character is repeated is n factorial over m minus n 43 00:03:49,769 --> 00:03:53,626 factorial. So, again m has got to be less than n in 44 00:03:53,626 --> 00:03:56,838 this. And not m in this but so that's, that's 45 00:03:56,838 --> 00:04:02,908 the number, that's what we just showed. So that's if we divide by m to the n, 46 00:04:02,908 --> 00:04:08,938 that's the probability that no character is repeated in a random m word of length 47 00:04:08,938 --> 00:04:11,566 n. It's the number that there were none 48 00:04:11,566 --> 00:04:16,870 repeated divided by the total number of possible or another way to look at that 49 00:04:16,870 --> 00:04:22,096 is, if we take them one at a time that's the same as the probability that, if we, 50 00:04:22,096 --> 00:04:27,400 if we take a sequence of, characters, or throw a sequence of balls in there and, 51 00:04:27,400 --> 00:04:32,704 it's the same as the probability that the first time we get a repeat positions it's 52 00:04:32,704 --> 00:04:36,080 bigger than n. Cause the probably the first n that 53 00:04:36,080 --> 00:04:40,688 there's no repeat is exactly that so it's a probability that the first repeat 54 00:04:40,688 --> 00:04:44,772 position is bigger then N. So now if we just sum that, we get the 55 00:04:44,772 --> 00:04:50,615 expected position of the first repeat. P some and it only goes up to the m 56 00:04:50,615 --> 00:04:55,370 because we're going to get repeat by the time we get m. 57 00:04:55,371 --> 00:05:02,800 So that's a familiar sum that's the Ramanujan, Ramanujan Qfunction that we 58 00:05:02,800 --> 00:05:09,225 looked at in lecture 4. And the result is square of pi, M over 2. 59 00:05:09,226 --> 00:05:17,424 Expected position of the first repeat is squared of pi M over 2 less the that 60 00:05:17,424 --> 00:05:23,181 analysis, completes the analysis of the birthday problem. 61 00:05:23,181 --> 00:05:31,063 So in our original problem if we had asked people, their birthdays. 62 00:05:31,063 --> 00:05:35,897 There's 365 days in a year. How many people do you have to ask before 63 00:05:35,897 --> 00:05:41,679 finding two with the same birthday? Well, you just have to compute square root 64 00:05:41,679 --> 00:05:47,110 of pi times 365 over 2 and it's about 24. So in a class of size 24, I've asked 65 00:05:47,110 --> 00:05:51,572 people one at a time, quite a bit bigger then 24 you've got a. 66 00:05:51,573 --> 00:05:56,977 A reasonable chance of finding the average number of people you have to ask before 67 00:05:56,977 --> 00:06:03,318 finding 2 with the same birthdays is 24. There's an analysis in the book that talks 68 00:06:03,318 --> 00:06:09,798 about how many you have to ask to have 50% chance that you have 2 with the same 69 00:06:09,798 --> 00:06:12,778 birthday. It's, it's about in the same range 70 00:06:12,778 --> 00:06:22,440 although that's a different problem. So that's, analytic combintorics with 71 00:06:22,440 --> 00:06:30,080 words. Take a look at the birthday problem.