Now we're going to look at a classical
combinatorial problem called the birthday
problem that you've probably heard in one
form or 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
should you ask, will you ask before you
find two that have the same birthday.
Well by the time you get to 365, then
you'll after you get, you know the next
one will have to have the same birthday as
someone else.
But usually it will happen much earlier.
So, the question is what can we expect on
average if say the birthdays are random.
So a way to look at this is a ball and urn
problem.
It's just, we've got m urns, so in this
case it would be 365 urns.
And we ask the birthday and the person
goes to 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 6th one that's where
we stop.
So if the balls come at random urns then
the question is how long until some urn
gets 2 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, each urn has either no
elements or just 1.
And so that's going to be the basis of, of
the analysis.
And the first question is how many
different birthday sequences are there?
So, again if, so m is our parameter.
That's the number of urns.
We want to know the, class of birthday
sequences and we'll have a generating
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 0 or 1 occurrence.
So, what's the construction for building
birthday sequences?
Well, it's pretty simple.
We have m urns.
We have a sequence of them.
And every urn is either empty, or has one
element.
That's the directly construction for
birthday sequences.
So, with the symbolic method that
translates immediately to the generating
function for e goes to 1, e goes to z,
sequence of m of them just raise it up to
the mth power.
So the EGF equation for birthday sequences
is 1 plus z to the n and then the counting
sequence is coefficient of n factorial in
that, so it, sorry, n factorial times
coefficient of z to the n in that.
Which is n factorial times m choose n
which, the n factorial cancels so it's m
factorial or m minus n factorial or the
product of m, m minus 1 down to m minus n
plus 1.
That's the number of different birthday
sequences.
So with that we can use to, to solve the
birthday problem so with this logic.
So we just showed that the number of n
character words where no character is
repeated is n factorial over m minus n
factorial.
So, again m has got to be less than n in
this.
And not m in this but so that's, 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 of
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,
if we take a sequence of, characters, or
throw a sequence of balls in there and,
it's the same as the probability that the
first time we get a repeat positions it's
bigger than n.
Cause the probably the first n that
there's no repeat is exactly that so it's
a probability that the first repeat
position is bigger then N.
So now if we just sum that, we get the
expected position of the first repeat.
P some and it only goes up to the m
because we're going to get repeat by the
time we get m.
So that's a familiar sum that's the
Ramanujan, Ramanujan Qfunction that we
looked at in lecture 4.
And the result is square of pi, M over 2.
Expected position of the first repeat is
squared of pi M over 2 less the that
analysis, completes the analysis of the
birthday problem.
So in our original problem if we had asked
people, their birthdays.
There's 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 2 and it's about 24.
So in a class of size 24, I've asked
people one at a time, quite a bit bigger
then 24 you've got a.
A reasonable chance of finding the average
number of people you have to ask before
finding 2 with the same birthdays is 24.
There's an analysis in the book that talks
about how many you have to ask to have 50%
chance that you have 2 with the same
birthday.
It's, it's about in the same range
although that's a different problem.
So that's, analytic combintorics with
words.
Take a look at the birthday problem.