1
00:00:00,012 --> 00:00:07,382
So here is a few exercises that you can
use to test your understanding material in

2
00:00:07,382 --> 00:00:12,516
this section.
So, first one is just a calculation.

3
00:00:12,516 --> 00:00:18,066
So, how many people would you think, if
you were a paranoid professor and you had

4
00:00:18,066 --> 00:00:23,778
a big class, how big would the class be to
be 99% sure that if you ask everybody in

5
00:00:23,778 --> 00:00:28,135
the class you're going to find two that
have the same birthday?

6
00:00:28,135 --> 00:00:33,280
So that's just a fun calculation.
So this next one is kind of a

7
00:00:33,280 --> 00:00:37,977
commonatorial thing.
It's actually the basis for Kunuth's

8
00:00:37,978 --> 00:00:43,193
analysis of linear probing.
And it ties together uh,some of the

9
00:00:43,193 --> 00:00:48,981
calculations that we did in this section
having to do with Kali trees.

10
00:00:48,981 --> 00:00:56,116
And it's actually easier than it looks.
So it's, proving this generalization of

11
00:00:56,116 --> 00:01:01,549
the binomial theorem, due to, Abel.
And it's worthwhile doing this, this

12
00:01:01,549 --> 00:01:05,268
calculation.
And then, here's an exercise that isn't in

13
00:01:05,268 --> 00:01:07,690
the book.
That, but it should be there.

14
00:01:07,690 --> 00:01:12,277
So I numbered it, number 99.
And it's to show that the probability.

15
00:01:12,277 --> 00:01:17,274
If you take a random mapping of size n.
What's the probability that, it doesn't

16
00:01:17,274 --> 00:01:22,039
have any singleton cycles.
Nothin' that maps to itself.

17
00:01:22,040 --> 00:01:27,536
Amazingly it turns out to be N over E the
same as the derangement problem for

18
00:01:27,536 --> 00:01:31,936
permutations.
There's no good reason that these things

19
00:01:31,937 --> 00:01:35,799
should be the same but it turns out not to
be the same.

20
00:01:35,799 --> 00:01:40,304
So that's a, a nice exercise for, for you
to take a look at.

21
00:01:40,304 --> 00:01:45,314
So, to finish up, read that part of the
text.

22
00:01:45,315 --> 00:01:53,569
Good idea to run empirical tests to see
if, Kunuth's analysis works, and you'll

23
00:01:53,569 --> 00:01:58,842
find that it does.
And it's also a good idea to, take a look

24
00:01:58,842 --> 00:02:06,161
at properties of mappings and check that,
the, analysis, works as well.

25
00:02:06,162 --> 00:02:11,293
And then maybe write up those solutions
to, those exercises.

26
00:02:11,293 --> 00:02:15,898
That's, the, end of analytic
combinatorics, part 1.

27
00:02:15,898 --> 00:02:22,554
We've done a pretty full survey of basic
techniques, introduced analytic

28
00:02:22,554 --> 00:02:28,854
combinatorics and shown how it applies to
the study of basic combinatorial

29
00:02:28,854 --> 00:02:35,254
structures like trees, permutations
strings words and mapping.

30
00:02:35,254 --> 00:02:43,739
We, we hope that as many of you are
interested enough in the, in the problems

31
00:02:43,739 --> 00:02:52,035
that we've looked at to sign up for
Analytic Combinatorics part 2, which'll

32
00:02:52,035 --> 00:02:54,155
start soon, thanks.