1
00:00:03,600 --> 00:00:06,899
Just want to finish up by talking little 
bit. 

2
00:00:06,899 --> 00:00:12,466
giving some perspective on the things 
that we've talked about so far today. 

3
00:00:12,466 --> 00:00:16,452
so 
the ideas that we have a, a calculus that 

4
00:00:16,452 --> 00:00:21,126
is going to be very effective for 
quantitative study of all kinds of a 

5
00:00:21,126 --> 00:00:26,143
large combinatorial structures. 
Always going through same kind of process 

6
00:00:26,143 --> 00:00:31,298
where we have a construction that 
translates to a generating function, that 

7
00:00:31,298 --> 00:00:36,578
translates to coefficient asymptotics. 
actually with complex asymptotics we 

8
00:00:36,578 --> 00:00:41,247
don't even have to solve explicitly for 
the generating function often. 

9
00:00:41,247 --> 00:00:46,850
merely the form of the equation is going 
to give the generating function that 

10
00:00:46,850 --> 00:00:51,519
[COUGH], is going to give a transfer 
theorem that gives the coefficient 

11
00:00:51,519 --> 00:00:56,993
asymptotics immediately. 
and just think about what we've talked 

12
00:00:56,993 --> 00:01:03,621
about in the last four lectures versus 
this lecture to count binary trees. 

13
00:01:03,621 --> 00:01:11,885
so we had a whole slide to go from the 
currents to generate function involving a 

14
00:01:11,885 --> 00:01:16,205
convolution. 
and then expanding that generating 

15
00:01:16,205 --> 00:01:22,498
function involves some kind of intricate 
calculations using binomial coefficients 

16
00:01:22,498 --> 00:01:27,103
that you might remember. 
and got us to the exact form of the 

17
00:01:27,103 --> 00:01:31,248
Catalan numbers. 
and then we had to do the asymptotics 

18
00:01:31,248 --> 00:01:36,774
using Sterling's Approximation that also 
involved significant amount of 

19
00:01:36,774 --> 00:01:40,842
calculations. 
you may remember the first time you saw 

20
00:01:40,842 --> 00:01:46,905
each one of these the amount of intricate 
calculation that seem to be involved. 

21
00:01:46,905 --> 00:01:50,855
Although there's straightforward from 
step to step. 

22
00:01:50,855 --> 00:01:56,431
there's a lot of steps with analytic 
combinatorics. we don't do those 

23
00:01:56,431 --> 00:02:00,363
calculations anymore. 
We simply create the combinatoric 

24
00:02:00,363 --> 00:02:04,295
instruction. 
get to the generating function equation 

25
00:02:04,295 --> 00:02:09,800
and then get the transfer theorem to get 
the asymptotic result, that we're 

26
00:02:09,800 --> 00:02:14,161
interested in. 
And these are normally very accurate and 

27
00:02:14,161 --> 00:02:18,165
certainly accurate enough for practical 
applications. 

28
00:02:18,165 --> 00:02:21,740
so we're in for the arrangements. 
in that case 

29
00:02:21,740 --> 00:02:28,316
we we don't even know 
I didn't even do the example of the 

30
00:02:28,316 --> 00:02:34,043
calculation it's so complicated but we 
get immediately to the coefficient 

31
00:02:34,043 --> 00:02:37,837
asymptpotics. 
And this is a good example of something 

32
00:02:37,837 --> 00:02:43,349
that is characteristic of analytic 
commontorics. Becuase we had a basic 

33
00:02:43,349 --> 00:02:49,505
construction, a permetation a set of 
cycles that we modified to work with the, 

34
00:02:49,505 --> 00:02:51,802
to, 
to get this this answer. 

35
00:02:51,802 --> 00:02:57,200
that's very common we start with some 
fundamental constructs. 

36
00:02:57,200 --> 00:03:01,056
They're a basic things that, that we want 
to study. 

37
00:03:01,056 --> 00:03:07,071
they're either elementary or they're 
trivial or they confirm our intuition. 

38
00:03:07,071 --> 00:03:12,990
and we, we understand them but we 
try to understand'em from the standpoint 

39
00:03:12,990 --> 00:03:18,548
of analytic commontorics. But then we can 
have compound constructs where we have a 

40
00:03:18,548 --> 00:03:24,433
set of cycles or a sequence of sets and 
so forth. and again those are only the 

41
00:03:24,433 --> 00:03:29,990
constructions that I've presented there's 
many, many other constructions available. 

42
00:03:29,990 --> 00:03:35,221
and those things there's lot's of 
possibilities. they'll tell us something 

43
00:03:35,221 --> 00:03:40,583
about the structure like a permetation is 
a set of cycles. and actually lots 

44
00:03:40,583 --> 00:03:44,310
classic commonotorics can be dealt with 
in this way. 

45
00:03:44,310 --> 00:03:49,613
And then there's variations like 
generalizing the arrangements by adding 

46
00:03:49,613 --> 00:03:56,442
another parameter. the possibilities 
immediately become almost unlimited and 

47
00:03:56,442 --> 00:04:02,254
not only that when we get to a generating 
function and equation, we often have a 

48
00:04:02,254 --> 00:04:08,647
universal law that will give us the 
asymptotics. there would be no way to go 

49
00:04:08,647 --> 00:04:14,459
in and get the, exact result and then do 
asymptotics from the exact result. 

50
00:04:14,459 --> 00:04:20,944
in principle you could do that because 
what underlies the analytic combinatorics 

51
00:04:20,944 --> 00:04:26,924
is a bunch of very simple techniques. 
But why would you if your goal is the 

52
00:04:26,924 --> 00:04:31,410
asymptotic result? 
so that's a, a, a very standard paradigm. 

53
00:04:31,410 --> 00:04:35,667
and also combinatorial parameters can be 
handled. 

54
00:04:35,667 --> 00:04:41,539
and we'll see lots of examples of that. 
so that is, we're not just counting 

55
00:04:41,539 --> 00:04:45,209
things. 
We're counting properties of things but 

56
00:04:45,209 --> 00:04:50,714
we talked about in the generating 
function lecture, about the concept of 

57
00:04:50,714 --> 00:04:55,485
cumulative cost where rather than 
computing averages by using 

58
00:04:55,485 --> 00:05:01,577
probabilities. What we do is we count up 
the total cost among all structures and 

59
00:05:01,577 --> 00:05:08,168
then divide and it's reducing 
finding an average for number expected in 

60
00:05:08,168 --> 00:05:13,948
a random object to, to counting problems. 
So, let, so for, to find the leaves on a 

61
00:05:13,948 --> 00:05:19,511
binary tree we count trees using the 
standard process to get to the estimate 

62
00:05:19,511 --> 00:05:24,641
of the Catalan numbers. 
but it turns out that the symbolic method 

63
00:05:24,641 --> 00:05:30,662
works for bivariate generating functions, 
so the same construction will give a 

64
00:05:30,662 --> 00:05:36,230
explicit, equation for the, total cost. 
So, that's the leafs in all trees, you 

65
00:05:36,230 --> 00:05:42,006
just keep track of, of the leafs and 
other variable, and the same construction 

66
00:05:42,006 --> 00:05:45,764
follows through. 
And then differentiated value doesn't 

67
00:05:45,764 --> 00:05:49,730
want to get the leafs on all trees the 
way we did before. 

68
00:05:49,730 --> 00:05:55,785
we're going to get again an explicit and 
then we have the immediate transfer for 

69
00:05:55,785 --> 00:06:00,066
that one too. 
so, we don't have to go into the detail 

70
00:06:00,066 --> 00:06:04,869
we have these two asymptotic results and 
then we just divide. 

71
00:06:04,869 --> 00:06:11,398
and that's how we get to N over four. 
And again, we can do this without all the 

72
00:06:11,398 --> 00:06:17,211
detail that we presented before. 
So this is the slide that I started up 

73
00:06:17,211 --> 00:06:23,439
with that maybe makes a little more sense 
now that we've gone through a number of 

74
00:06:23,439 --> 00:06:26,552
examples. 
You need a lot of combinatorics. 

75
00:06:26,552 --> 00:06:29,742
We begin with combinatorial 
constructions. 

76
00:06:29,742 --> 00:06:34,450
We use symbolic transfer theorems to get 
generating functions. 

77
00:06:34,450 --> 00:06:39,784
They're the central object of study 
because we transferred to them from 

78
00:06:39,784 --> 00:06:45,219
combinatorial constructions and we 
extract coefficients from them using 

79
00:06:45,219 --> 00:06:49,947
analytic transfer theorems. 
and so we can, in principle we can do 

80
00:06:49,947 --> 00:06:55,947
this to any precision on the standard 
scale, and we can handle variations as 

81
00:06:55,947 --> 00:06:59,864
well. 
So now for the rest of the course, we're 

82
00:06:59,864 --> 00:07:05,764
going to be looking at many applications 
of analytic combinatorix for first we'll 

83
00:07:05,764 --> 00:07:11,872
do trees and then we'll do permutations 
which actually can be represented as a 

84
00:07:11,872 --> 00:07:16,731
certain kind of labeled trees. 
and we'll talk about bit streams and 

85
00:07:16,731 --> 00:07:22,353
associated data structures in mappings 
which are fascinating structures. 

86
00:07:22,353 --> 00:07:27,281
and these all have applications to the 
analysis of algorithms. 

87
00:07:27,281 --> 00:07:31,490
so that's what we'll be doing for the 
rest of the course. 

88
00:07:31,490 --> 00:07:35,978
so that's a perspective on what we've 
been doing 

89
00:07:35,978 --> 00:07:42,711
I just want to finish with some exercises 
that you might do to cement your 

90
00:07:42,711 --> 00:07:48,236
understanding of this material. 
So exercise 5.1 is how many good 

91
00:07:48,236 --> 00:07:55,487
strengths of length N have no occurrence 
of three zeros and that's a fine exercise 

92
00:07:55,487 --> 00:08:02,479
to try out these techniques on. 
were for trees and this is just again to 

93
00:08:02,479 --> 00:08:08,293
go through the steps of 
[COUGH] annalytic combinatorix for 

94
00:08:08,293 --> 00:08:14,019
problems similar to the ones that we did. 
So this is binary tree, where the size is 

95
00:08:14,019 --> 00:08:17,371
the total number of nodes internal and 
external. 

96
00:08:17,371 --> 00:08:23,725
so there is no even number is always an 
odd number of total number of nodes in so 

97
00:08:23,725 --> 00:08:26,956
we get an expression for that 
permutations. 

98
00:08:26,956 --> 00:08:30,663
what about, when the cycles are of odd 
lengths, 

99
00:08:30,663 --> 00:08:33,372
that's an easy one. 
tree parameters. 

100
00:08:33,372 --> 00:08:39,503
so the red notes here have both children 
internal and the blue ones have one 

101
00:08:39,503 --> 00:08:44,350
internal and one external. 
So what's the average number of red notes 

102
00:08:44,350 --> 00:08:48,057
and blue notes? 
We already did the average number of 

103
00:08:48,057 --> 00:08:53,191
leaves is it N over four. 
so the those some more problem. So for 

104
00:08:53,191 --> 00:08:58,540
the next lecture if you write up 
solutions to those excercise and read the 

105
00:08:58,540 --> 00:09:04,958
analytic combonatorix chapter in the text 
you'll have a good feeling for the basis 

106
00:09:04,958 --> 00:09:10,949
for, of the analysis of algorithms that 
we're going to begin starting in the next 

107
00:09:10,949 --> 00:09:11,520
lecture.