So here is a few exercises that you can
use to test your understanding material in
this section.
So, first one is just a calculation.
So, how many people would you think, if
you were a paranoid professor and you had
a big class, how big would the class be to
be 99% sure that if you ask everybody in
the class you're going to find two that
have the same birthday?
So that's just a fun calculation.
So this next one is kind of a
commonatorial thing.
It's actually the basis for Kunuth's
analysis of linear probing.
And it ties together uh,some of the
calculations that we did in this section
having to do with Kali trees.
And it's actually easier than it looks.
So it's, proving this generalization of
the binomial theorem, due to, Abel.
And it's worthwhile doing this, this
calculation.
And then, here's an exercise that isn't in
the book.
That, but it should be there.
So I numbered it, number 99.
And it's to show that the probability.
If you take a random mapping of size n.
What's the probability that, it doesn't
have any singleton cycles.
Nothin' that maps to itself.
Amazingly it turns out to be N over E the
same as the derangement problem for
permutations.
There's no good reason that these things
should be the same but it turns out not to
be the same.
So that's a, a nice exercise for, for you
to take a look at.
So, to finish up, read that part of the
text.
Good idea to run empirical tests to see
if, Kunuth's analysis works, and you'll
find that it does.
And it's also a good idea to, take a look
at properties of mappings and check that,
the, analysis, works as well.
And then maybe write up those solutions
to, those exercises.
That's, the, end of analytic
combinatorics, part 1.
We've done a pretty full survey of basic
techniques, introduced analytic
combinatorics and shown how it applies to
the study of basic combinatorial
structures like trees, permutations
strings words and mapping.
We, we hope that as many of you are
interested enough in the, in the problems
that we've looked at to sign up for
Analytic Combinatorics part 2, which'll
start soon, thanks.