1
00:00:03,720 --> 00:00:07,960
We're going to finish off by looking at 
the idea of. 

2
00:00:07,960 --> 00:00:11,118
Counting directly with generating 
functions. 

3
00:00:11,118 --> 00:00:16,214
This is going to be first step to ease us 
into really important role that 

4
00:00:16,214 --> 00:00:20,162
generating functions play, in analytic 
combinatorics. 

5
00:00:20,162 --> 00:00:26,192
so it's a, so it's a really an alternate 
view of what generating functions can do 

6
00:00:26,192 --> 00:00:31,647
for us, and it is very combinatorial. 
I will be much more formal, thorough and 

7
00:00:31,647 --> 00:00:37,676
extensive coverage of this, but still it 
is good to look at the same problem then, 

8
00:00:37,676 --> 00:00:41,840
we just looked at from this point of view 
in this lecture. 

9
00:00:41,840 --> 00:00:47,075
So what we're going to do is define a 
class of combinatorial objects that have 

10
00:00:47,075 --> 00:00:51,516
an associated size function. 
And the generating function's going to be 

11
00:00:51,516 --> 00:00:56,354
a sum over all members of the class. 
We'll still get to the same point of 

12
00:00:56,354 --> 00:01:00,795
getting a, an equation that's, a 
generating function must satisfy. 

13
00:01:00,795 --> 00:01:04,307
And from that point on, the analysis will 
be the same. 

14
00:01:04,307 --> 00:01:10,272
but getting that equation is much more 
natural and fundamental with this kind of 

15
00:01:10,272 --> 00:01:13,188
correspondence. 
It seems kind of abstract. 

16
00:01:13,188 --> 00:01:15,840
But, so, let's look at a specific 
example. 

17
00:01:15,840 --> 00:01:19,540
So lets say T is a set of all binary 
trees. 

18
00:01:19,540 --> 00:01:23,000
then we're going to define a size 
function. 

19
00:01:23,000 --> 00:01:28,657
that looks like absolute value. 
if you have any binary tree, it's going 

20
00:01:28,657 --> 00:01:32,780
to be the number of internal nodes in 
that tree. 

21
00:01:32,780 --> 00:01:39,912
[COUGH] Now, what we're interested in is 
a counting sequence and that's what we're 

22
00:01:39,912 --> 00:01:45,242
interested in before. 
It's the number of binary trees from the 

23
00:01:45,242 --> 00:01:50,337
set of all binary trees that have size 
function equal to n. 

24
00:01:50,337 --> 00:01:55,275
So, the, that's the number of binary 
trees with n internal nodes. 

25
00:01:55,275 --> 00:02:01,311
That what we were counting before. 
This is just a, a formal definition, tree 

26
00:02:01,311 --> 00:02:03,898
by tree. 
Now, what's that good for? 

27
00:02:03,898 --> 00:02:07,775
Well. 
If we define the generating function to 

28
00:02:07,775 --> 00:02:14,224
be the sum over all possible trees, of Z 
to the size of the tree, then that, 

29
00:02:14,224 --> 00:02:17,744
treats each term individually 
[COUGH]. 

30
00:02:17,744 --> 00:02:24,273
Each tree contributes individually to a 
term in the generating function, but it's 

31
00:02:24,273 --> 00:02:30,882
exactly the same as if the trees of size 
N were collected together and counted by 

32
00:02:30,882 --> 00:02:34,751
T sub N. 
So that's a fundamental idea on, of this 

33
00:02:34,751 --> 00:02:38,298
equation we, some over all possible 
trees. 

34
00:02:38,298 --> 00:02:44,584
but since it's Z to the size of the tree, 
all the ones of the same size are going 

35
00:02:44,584 --> 00:02:50,630
to contribute to the coefficient of that 
size, say N, and give us T sub N. 

36
00:02:50,630 --> 00:02:56,026
so it's the same generating function 
looked at a different way. 

37
00:02:56,026 --> 00:03:02,907
And so and the reason that's helpful is 
that [COUGH] we can look at the way that 

38
00:03:02,907 --> 00:03:09,306
we define the combinatorial structures. 
to give us the equation that we want for 

39
00:03:09,306 --> 00:03:14,867
the generating function. 
and so, this is how it works for binary 

40
00:03:14,867 --> 00:03:21,542
trees so definition of a binary tree. 
with [COUGH] is that it's a root node 

41
00:03:21,542 --> 00:03:26,997
with a binary tree on the left and a 
binary tree on the right. 

42
00:03:26,997 --> 00:03:32,285
and say on the left there's T sub L 
internal nodes, 

43
00:03:32,285 --> 00:03:35,978
on the right there's T sub R internal 
nodes. 

44
00:03:35,978 --> 00:03:43,363
if we take that sum of all possible trees 
and it's got all possible left nodes. 

45
00:03:43,363 --> 00:03:50,845
All possible right nodes then but we had 
[COUGH] Z to the size of the whole tree 

46
00:03:50,845 --> 00:03:55,060
that's the size of the left, the size of 
the right, +1. 

47
00:03:55,060 --> 00:04:01,512
So, the decomposition that we use to 
define what we mean by, what is a binary 

48
00:04:01,512 --> 00:04:05,350
tree? 
immediately gives this equation on the 

49
00:04:05,350 --> 00:04:10,169
generating function. 
there's, it starts out with a one. 

50
00:04:10,169 --> 00:04:14,252
That's, for the empty tree that doesn't 
compose. 

51
00:04:14,252 --> 00:04:18,336
So the double sum is for non empty trees. 
so 

52
00:04:18,336 --> 00:04:22,420
that's a first key step to understand 
that the, 

53
00:04:22,420 --> 00:04:27,315
And the decomposition, the recursive 
decomposition, the way that we define 

54
00:04:27,315 --> 00:04:32,480
binary trees, immediately translates to 
an equation on the generated function. 

55
00:04:32,480 --> 00:04:38,949
so now that equation, those T sub N and T 
sub R are just afformal variables and 

56
00:04:38,949 --> 00:04:44,505
they're independent, so, we can 
immediately split that sum up into Z 

57
00:04:44,505 --> 00:04:51,354
times sum overall Teesabellsi to the T 
sub L over all T sub R the T sub R and 

58
00:04:51,354 --> 00:04:56,530
then get the answer that T of Z equals, 
one plus Z, T of Z squared. 

59
00:04:56,530 --> 00:05:02,079
Just the same as we found before by 
worrying about all the counting, but this 

60
00:05:02,079 --> 00:05:06,332
is much more direct. 
Really the equation says that, a binary 

61
00:05:06,332 --> 00:05:10,585
tree is empty or it's a root connected to 
two binary trees. 

62
00:05:10,585 --> 00:05:16,423
And actually we're going to see a very 
formal way to really go right from the 

63
00:05:16,423 --> 00:05:21,901
[COUGH] description of what it is right 
down to that generating function 

64
00:05:21,901 --> 00:05:27,992
equation. 
so here's another way to look at it, just 

65
00:05:27,992 --> 00:05:33,881
to make sure so the generating function 
is really got a term for each tree. 

66
00:05:33,881 --> 00:05:38,336
So those are all the possible trees and 
it just keeps going. 

67
00:05:38,336 --> 00:05:44,678
So each tree of size 3 is represented. 
It's a sum over all trees, Z to that tree 

68
00:05:44,678 --> 00:05:48,605
size. 
now when we're worrying about the counts, 

69
00:05:48,605 --> 00:05:54,267
we're just collecting all the terms for 
the same exponent, we're just doing the 

70
00:05:54,267 --> 00:05:57,512
algebra. 
so 

71
00:05:57,512 --> 00:06:01,819
now but if you multiply TTfz, of Z * T of 
Z, it's like taking two trees and 

72
00:06:01,819 --> 00:06:06,273
composing them. 
Well that's what we mean by binary tree, 

73
00:06:06,273 --> 00:06:09,193
take two trees and compose them. 
. 

74
00:06:09,193 --> 00:06:13,282
so T1+zT(z^2), of Z = 1 + ZT^2, If we 
write the things out symbolically as 

75
00:06:13,282 --> 00:06:19,269
trees then you can see immediately that 
this tree here comes from one of those, 

76
00:06:19,269 --> 00:06:24,839
and one of those and so forth. 
it's in fact, some mathematicians prefer 

77
00:06:24,839 --> 00:06:30,632
to work with, the symbols in, in some 
cases in, in commonotorics, people, go 

78
00:06:30,632 --> 00:06:34,633
very far working with completely symbolic 
representations. 

79
00:06:34,633 --> 00:06:39,667
It's a good way to think about it, it's, 
there's a term in that generating 

80
00:06:39,667 --> 00:06:45,254
function corresponding to each tree, when 
we're trying to find out how many there 

81
00:06:45,254 --> 00:06:50,220
were of each size, we're just doing the 
algebra of, collecting by size. 

82
00:06:50,220 --> 00:06:56,869
Now, that's, important, but there's, 
another idea that is related to this, 

83
00:06:56,869 --> 00:07:01,562
that, I want to introduce, and that's all 
about cost. 

84
00:07:01,562 --> 00:07:08,133
So a lot of times, it's not just about 
the size, it's about some other property 

85
00:07:08,133 --> 00:07:13,062
of the, of the structure. 
and so so, we'll use, we'll do two 

86
00:07:13,062 --> 00:07:15,799
examples. 
One's a very easy example. 

87
00:07:15,799 --> 00:07:20,024
How many one bits are there in a random 
bit stream? 

88
00:07:20,024 --> 00:07:23,465
Well 
everybody knows it should be about half. 

89
00:07:23,465 --> 00:07:28,049
but still that'll be a warm up. 
We'll get the right answer for that. 

90
00:07:28,049 --> 00:07:34,120
A more complicated thing is 
that's [COUGH] if we're using a binary 

91
00:07:34,120 --> 00:07:39,953
tree in a computer representation, it's 
important to know how many of the nodes 

92
00:07:39,953 --> 00:07:45,288
have both leaves external. 
you can save space in that way in a lot 

93
00:07:45,288 --> 00:07:49,485
of situations. 
so if we have a random binary tree, how 

94
00:07:49,485 --> 00:07:53,431
many leaves are there? 
then maybe that's not so easy. 

95
00:07:53,431 --> 00:07:59,206
in fact with generating functions we can 
have a unified approach to studying 

96
00:07:59,206 --> 00:08:03,392
perameters. 
and again that's one of the key benefits 

97
00:08:03,392 --> 00:08:07,795
of the way, analytic combinatorics way of 
looking at things. 

98
00:08:07,795 --> 00:08:14,074
and I want to do these examples to show 
the advantages of using generating 

99
00:08:14,074 --> 00:08:18,700
functions to help us do 
calculations and analysis like this. 

100
00:08:18,700 --> 00:08:23,964
so again it's the same kind of idea. 
We're going to have a class it's, the 

101
00:08:23,964 --> 00:08:27,281
same idea. 
We're going to have a class of 

102
00:08:27,281 --> 00:08:31,896
combinatorial objects. 
our model is going to be that all objects 

103
00:08:31,896 --> 00:08:36,801
of each size are equally likely. 
and that's realistic in a lot of 

104
00:08:36,801 --> 00:08:40,705
situations. 
so lets look at how the calculations look 

105
00:08:40,705 --> 00:08:44,080
when we're trying to find the value of a 
parameter. 

106
00:08:44,080 --> 00:08:50,532
so let's say the all, set of all objects 
in the class is p and then we have a size 

107
00:08:50,532 --> 00:08:55,353
function which, for every object in the 
class, we have a defined size. 

108
00:08:55,353 --> 00:09:01,167
then we have the counting function so 
that's the number of objects that have a 

109
00:09:01,167 --> 00:09:04,712
size n. 
so that's what we've been talking about 

110
00:09:04,712 --> 00:09:08,824
up to this point. 
but now let's say we also have a cost 

111
00:09:08,824 --> 00:09:15,789
associated with each object. 
And then, in that case we're going to be 

112
00:09:15,789 --> 00:09:22,680
interested in the number of objects that 
have a given size and a given cost. 

113
00:09:22,680 --> 00:09:29,003
And, were, want to know that, so we can 
do the calculation of the average value. 

114
00:09:29,003 --> 00:09:35,326
So that is the expected cost of an object 
of size n, is going to be the probability 

115
00:09:35,326 --> 00:09:39,436
that the object cost of an object of size 
n is k. 

116
00:09:39,436 --> 00:09:44,653
which is the number that F costs K 
divided by the total number. 

117
00:09:44,653 --> 00:09:48,447
then we're assuming their all equally 
likely. 

118
00:09:48,447 --> 00:09:53,190
times k so that's the definition of the 
expected cost. 

119
00:09:53,190 --> 00:10:00,447
and so that's all a familiar calculation 
if we know all these quantities. 

120
00:10:00,447 --> 00:10:06,046
But what. 
This point of view buys for us is, well 

121
00:10:06,046 --> 00:10:13,510
let's notice that we can factor out the p 
sub n, and we can just count up the total 

122
00:10:13,510 --> 00:10:15,809
cost. 
of all objects of size n. 

123
00:10:15,809 --> 00:10:19,112
That's called the cumulative, the 
accumulated cost. 

124
00:10:19,112 --> 00:10:22,481
so every object's got a cost associated 
with it. 

125
00:10:22,481 --> 00:10:25,520
and then we take all the objects of size 
n. 

126
00:10:25,520 --> 00:10:30,113
Add up all their costs. 
And divide that by the number of objects 

127
00:10:30,113 --> 00:10:37,010
of size n that's the expected cost. 
It's a trivial calculation but still it's 

128
00:10:37,010 --> 00:10:42,557
an, an important distinction. 
so the, the idea is we, if we can compute 

129
00:10:42,557 --> 00:10:48,629
the accumulated costs, then we can get 
the expected costs just by dividing the 

130
00:10:48,629 --> 00:10:51,777
accumulated cost by the number of 
objects. 

131
00:10:51,777 --> 00:10:55,975
now what's that have to do with 
generating functions? 

132
00:10:55,975 --> 00:11:01,234
Well again [COUGH]. 
we start out with the, same situation. 

133
00:11:01,234 --> 00:11:05,091
let's take a look at the generating 
functions. 

134
00:11:05,091 --> 00:11:10,443
So we have already talked about the 
counting generating function. 

135
00:11:10,443 --> 00:11:17,684
If we sum over all objects in the class Z 
to their size, then just algebra collects 

136
00:11:17,684 --> 00:11:23,744
their terms to get the [COUGH] 
coefficient of Z to the N as the number 

137
00:11:23,744 --> 00:11:27,680
of objects of size N. 
but we can have a similar. 

138
00:11:27,680 --> 00:11:31,990
Generating function to compute the 
cumulated cost. 

139
00:11:31,990 --> 00:11:38,350
If we look at the function c of z which 
is the sum for every object in the class. 

140
00:11:38,350 --> 00:11:44,170
Its cost times Z to the size. 
Then, those things are going to 

141
00:11:44,170 --> 00:11:49,131
collect by size. 
And so the coefficient of z^n in that is 

142
00:11:49,131 --> 00:11:56,168
going to be nothing other than for all 
values of k, the sum of k times p and k. 

143
00:11:56,168 --> 00:12:00,498
It just collects the objects of cross k 
by size. 

144
00:12:00,498 --> 00:12:05,640
And it will get them all. 
So the coefficient of z^n in that 

145
00:12:05,640 --> 00:12:09,520
function c(z) is exactly the accumulated 
cost. 

146
00:12:09,520 --> 00:12:15,085
So that gives us the average cost. 
We just extract coefficients from those 

147
00:12:15,085 --> 00:12:18,620
two generating functions. 
the bottom line is. 

148
00:12:18,620 --> 00:12:24,046
If we want to compute the expected value 
of a cost, we have two GF counting 

149
00:12:24,046 --> 00:12:26,867
problems to solve. 
and their similar. 

150
00:12:26,867 --> 00:12:33,089
we know how to solve we've already done 
examples where we can solve GF counting 

151
00:12:33,089 --> 00:12:36,417
problems. 
And now we can get average values of 

152
00:12:36,417 --> 00:12:39,528
parameters by solving GF counting 
problems. 

153
00:12:39,528 --> 00:12:44,166
so again, it's a, it's a. 
We, at trivial calculation, to say, we're 

154
00:12:44,166 --> 00:12:49,607
going to compute the average by computing 
the total and divide by the number. 

155
00:12:49,607 --> 00:12:53,988
But still, it's fundamental because now 
everything is counting. 

156
00:12:53,988 --> 00:12:58,370
And we're going to have very powerful 
mechanisms for counting. 

157
00:12:58,370 --> 00:13:02,892
So let's see how it works for the two 
examples that I mentioned. 

158
00:13:02,892 --> 00:13:09,022
How many one bits in a random bit stream? 
Okay so these are sort of orbit strings. 

159
00:13:09,022 --> 00:13:15,035
the number of bits is our size function 
so that's going to be the size function 

160
00:13:15,035 --> 00:13:21,424
for any bit string then in with the cost 
functional B will call ones B that's the 

161
00:13:21,424 --> 00:13:27,888
number of one bits in a given bit string. 
number of bit strings of size n that's 

162
00:13:27,888 --> 00:13:29,847
besoben. 
and that's 2n. 

163
00:13:29,847 --> 00:13:35,997
[COUGH], and then CeceVan, we can use GS 
to get that, but, no let's no, no hit, 

164
00:13:35,997 --> 00:13:41,029
and we're happy with that. 
And then, the'cumulated cost function 

165
00:13:41,029 --> 00:13:46,620
Cece Van, is the total number of one bits 
in all bit strings of size N. 

166
00:13:46,620 --> 00:13:55,258
So counting g f, so that's b of z, sum 
over all bitstrings z to its size and 

167
00:13:55,258 --> 00:14:02,093
that's equal to two to the n, z to the n. 
One over two, one over 1-2z. 

168
00:14:02,093 --> 00:14:08,081
so that's, b of z. 
And actually, we can, get that formally 

169
00:14:08,081 --> 00:14:13,711
just from the definitions. 
But, I'm sure you believe that one. 

170
00:14:13,711 --> 00:14:18,270
what about the cumulative cost GF? 
So, [COUGH]. 

171
00:14:18,270 --> 00:14:23,654
So that's that's the function. 
so now, what we want to do is similar to 

172
00:14:23,654 --> 00:14:28,613
what we did for the Catalan. 
Is to use a, a recursive description of 

173
00:14:28,613 --> 00:14:32,935
what a bit string is, to get us a, a 
formula for this function. 

174
00:14:32,935 --> 00:14:37,823
And well, what's a bit string? 
It's either a zero or a one, followed by 

175
00:14:37,823 --> 00:14:42,560
another bit string. 
So [COUGH], for if we're going to have 

176
00:14:42,560 --> 00:14:47,926
for all bits strings the number of 1's. 
That's going to be e-, equal to. 

177
00:14:47,926 --> 00:14:53,923
for all bit strings you can put a zero or 
a one in the front and that, that'll give 

178
00:14:53,923 --> 00:14:58,841
you all possible bit strings. 
In this whole set of bit strings there's 

179
00:14:58,841 --> 00:15:01,009
one, one bit. 
plus there's two. 

180
00:15:01,009 --> 00:15:05,018
How ever many one bits there are in the 
bit string b prime. 

181
00:15:05,018 --> 00:15:09,299
And that's summed over all b, b prime. 
And we had, length of b. 

182
00:15:09,299 --> 00:15:14,464
But it's the length of b prime, plus one. 
So again, that recursive description 

183
00:15:14,464 --> 00:15:18,473
immediately gives that formula for the 
accumulated cost, GF. 

184
00:15:18,473 --> 00:15:24,991
And so now, just doing the math. 
that the first term gives us a ZV of Z, 

185
00:15:24,991 --> 00:15:31,924
and the second term gives us a 2Z C of Z. 
So that's an equation for the accumulated 

186
00:15:31,924 --> 00:15:35,567
cost function and we've got the what B of 
Z is. 

187
00:15:35,567 --> 00:15:39,210
And so we can just solve that equation. 
It's 

188
00:15:39,210 --> 00:15:46,127
[COUGH] Zb of Z is one over one minus 2Z. 
And then C of Z, bring 2Z Cof C over to 

189
00:15:46,127 --> 00:15:51,447
the left hand side. 
And so we divide by another factor of 1 - 

190
00:15:51,447 --> 00:15:54,861
2Z. 
and so that's a proof that C of Z is 

191
00:15:54,861 --> 00:16:01,192
equal to Z over 1 - 2C squared. 
So now we have explicit expressions for 

192
00:16:01,192 --> 00:16:05,517
both the enumerating GF and the 
accumulated cost GF. 

193
00:16:05,517 --> 00:16:11,792
And all we need to do is extract 
coefficients from those two functions in 

194
00:16:11,792 --> 00:16:15,693
order to get the average cost. 
2zz/(1-2*z^2) / 1 - 2z^2 is, that's a 

195
00:16:15,693 --> 00:16:21,290
standard generating function that we've 
seen several times before. 

196
00:16:21,290 --> 00:16:26,971
And so the bottom line is, the 
coefficient of z^n and the accumulated 

197
00:16:26,971 --> 00:16:31,274
cost is n*2^n. 
N minus one, coefficient is z to the n, 

198
00:16:31,274 --> 00:16:34,060
in 
[COUGH] and the numeration is to the N, 

199
00:16:34,060 --> 00:16:37,650
and that gives us the result that the 
expected cost is N over two. 

200
00:16:37,650 --> 00:16:41,836
Again that's a warm up we kind of knew 
its n over two. 

201
00:16:41,836 --> 00:16:48,347
now lets do a problem that you might have 
a lot of difficulty solving some other 

202
00:16:48,347 --> 00:16:54,704
way and that's these in binary trees. 
So again a leaf in a binary tree is an 

203
00:16:54,704 --> 00:16:58,580
internal node whose children of both are 
external. 

204
00:16:58,580 --> 00:17:05,301
so [COUGH] for example, in the trees of 
size two, each one of them has one, leaf. 

205
00:17:05,301 --> 00:17:09,236
So the 
if we wanted to go down to do all the 

206
00:17:09,236 --> 00:17:13,252
counts, 
So, t of n's the number of binary trees 

207
00:17:13,252 --> 00:17:17,761
with n nodes. 
TNK is the number of n known binary trees 

208
00:17:17,761 --> 00:17:19,892
with k leaves. 
So, T2-1 =two. 

209
00:17:19,892 --> 00:17:26,777
There's two of them that have one leaf. 
and CN is the average number of leaves in 

210
00:17:26,777 --> 00:17:31,778
a random n node binary tree. 
So that's the ratio of those two. 

211
00:17:31,778 --> 00:17:36,043
So C21. 
= 1 so for five there's four of them that 

212
00:17:36,043 --> 00:17:41,934
have one leaf, so 
I'm sorry for three, there's four of them 

213
00:17:41,934 --> 00:17:48,838
that have one leaf, so T31 equals four. 
There's one, the balanced one, has two 

214
00:17:48,838 --> 00:17:51,783
leaves, so T31 equals one. 
And so, 

215
00:17:51,783 --> 00:17:58,084
[COUGH] if you want to compute the 
average number of leaves in a binary tree 

216
00:17:58,084 --> 00:18:03,570
with three nodes, it's four plus two 
times one divided by five, or 1.2. 

217
00:18:03,570 --> 00:18:08,825
And similarly for fourteen, we find that 
eight of them have one leaf and six of 

218
00:18:08,825 --> 00:18:12,226
them will have two leaves and that gives 
a solution. 

219
00:18:12,226 --> 00:18:16,801
So what's the average number of leaves in 
a, in, in a random binary tree? 

220
00:18:16,801 --> 00:18:21,191
If we treat them all likely how do we get 
that counting sequence? 

221
00:18:21,191 --> 00:18:26,818
and again, that's actually a practical 
problem that plagued programmers when 

222
00:18:26,818 --> 00:18:32,506
binary trees first came into use because 
these things were a wasteful of space and 

223
00:18:32,506 --> 00:18:35,660
people want to know how much space they 
could save. 

224
00:18:35,660 --> 00:18:40,000
O.k. 
So let's [COUGH] use cumulative counting 

225
00:18:40,000 --> 00:18:43,200
to solve that problem. 
So. 

226
00:18:43,200 --> 00:18:49,916
set of all binary trees internal nodes is 
a size function leaves is our cost 

227
00:18:49,916 --> 00:18:56,028
function number of leaves in the tree. 
the number of binary trees is size n of 

228
00:18:56,028 --> 00:19:02,443
catalyn numbers as c analyses that we did 
and now what we want to do is develop a 

229
00:19:02,443 --> 00:19:08,556
generating function for the cumulative 
cause which is the total number of leaves 

230
00:19:08,556 --> 00:19:14,966
in all binary trees of size n. 
so the counting GF, we already did that 

231
00:19:14,966 --> 00:19:18,836
one. 
so that's just summarizing that. 

232
00:19:18,836 --> 00:19:26,760
and the accumulated cost GF, that's for 
the [COUGH] at c of z sum over all trees, 

233
00:19:26,760 --> 00:19:32,938
number of leaves times z to the size. 
[COUGH], and then, the average number of 

234
00:19:32,938 --> 00:19:38,013
leaves in a random endo binary tree is 
just the ratio of the coefficients of 

235
00:19:38,013 --> 00:19:40,979
those. 
We already know the coefficient of the 

236
00:19:40,979 --> 00:19:43,747
number of trees, that's the catalyn 
number. 

237
00:19:43,747 --> 00:19:47,900
So, we're looking for coefficient of Z to 
be in in C of C. 

238
00:19:47,900 --> 00:19:52,531
So, that's the next thing we're going to 
do is try to find that cumulative cost 

239
00:19:52,531 --> 00:19:56,176
function. 
so [COUGH] that's the, that's the 

240
00:19:56,176 --> 00:20:00,220
function. 
Now again we're going to use the same. 

241
00:20:00,220 --> 00:20:04,601
kind of decomposition that we did when 
we're enumerating trees. 

242
00:20:04,601 --> 00:20:07,788
And, and actually usually, that's what 
happens. 

243
00:20:07,788 --> 00:20:13,165
The, same formal description, that gave 
us the number of trees, it's going to 

244
00:20:13,165 --> 00:20:17,149
give us, the cost. 
And that's why this methods so powerful. 

245
00:20:17,149 --> 00:20:22,460
we, we, do the work to figure out the 
composition, of the way to describe it. 

246
00:20:22,460 --> 00:20:27,439
and then we get to apply it twice. 
Once to find out the total number, and 

247
00:20:27,439 --> 00:20:30,560
the other to find out the total cost. 
and so. 

248
00:20:30,560 --> 00:20:38,714
[COUGH] that the composition immediately 
leads to this equation for the cumulated 

249
00:20:38,714 --> 00:20:44,360
generating function. 
So there's the tree that is just a leaf. 

250
00:20:44,360 --> 00:20:52,150
so that's accounts for the Z term. 
and then for all the other trees there's 

251
00:20:52,150 --> 00:20:57,511
a left and a right. 
So that's T sub L nodes on the left and T 

252
00:20:57,511 --> 00:21:03,208
sub L nodes on the right. 
and however many leaves they are on the 

253
00:21:03,208 --> 00:21:08,044
left [COUGH] they're. 
In the tree, is the total number of 

254
00:21:08,044 --> 00:21:12,751
leaves on the left, plus the total number 
of leaves on the right. 

255
00:21:12,751 --> 00:21:19,592
The leaf can't, if it's got more than one 
node in it, the leaf can't cross between 

256
00:21:19,592 --> 00:21:23,931
the two trees. 
so, this equation here holds exactly. 

257
00:21:23,931 --> 00:21:29,963
Again, the plus one for the root but that 
same decomposition gives us this same 

258
00:21:29,963 --> 00:21:33,125
equation. 
And again, T sub L and T sub R are 

259
00:21:33,125 --> 00:21:41,874
independent so that immediately [COUGH]. 
allows us to break these break these sums 

260
00:21:41,874 --> 00:21:49,339
up into independent sums. 
So we have leaves of t sub l, z to the t 

261
00:21:49,339 --> 00:21:53,957
c l, t sub l. 
times the sum on T sub R there's, two 

262
00:21:53,957 --> 00:22:00,844
terms that are similar, one where we, for 
the T sub L and one for the, T sub R and 

263
00:22:00,844 --> 00:22:07,078
then, and then we have the double sum, so 
we distribute over those, so that's just 

264
00:22:07,078 --> 00:22:13,312
elementary distribution, and then those 
things, we have expressions for every one 

265
00:22:13,312 --> 00:22:17,372
of them, 
leafs of T sub L Z, to the T sub L that's 

266
00:22:17,372 --> 00:22:21,030
Z of Z. 
And sum t sub r t z to the t sub r, 

267
00:22:21,030 --> 00:22:26,871
that's t of z and we have two of those. 
So that gives us [COUGH] a simple 

268
00:22:26,871 --> 00:22:31,590
equation for. 
Z of Z, the in-cumulative generated 

269
00:22:31,590 --> 00:22:34,612
function. 
All that's left is to extract 

270
00:22:34,612 --> 00:22:38,255
co-coefficient's from that generating 
function. 

271
00:22:38,255 --> 00:22:42,207
So this is the summary of the deriration 
so far. 

272
00:22:42,207 --> 00:22:47,942
we're looking for that CGF. 
we did that decomposition, and we have an 

273
00:22:47,942 --> 00:22:52,205
equation for it. 
we know the number of tree's is the 

274
00:22:52,205 --> 00:22:56,656
catalan numbers. 
and so our accumulated generating 

275
00:22:56,656 --> 00:23:02,260
function is c of z, z plus 2z, t of z c 
of z, and we solve for z of c. 

276
00:23:02,260 --> 00:23:08,351
We get z over one minus 2c t of z. 
catalan numbers multiplied by 2z then 

277
00:23:08,351 --> 00:23:12,900
subtract one, you get z over square root 
of one minus 4z. 

278
00:23:12,900 --> 00:23:17,709
So that's an explicit expression for the 
cumulated cost function. 

279
00:23:17,709 --> 00:23:23,332
C of Z equals Z / 1 - 4Z. 
And we can extract coefficients from that 

280
00:23:23,332 --> 00:23:28,956
the same way that we did for the Catalan 
numbers using the binomial theorem. 

281
00:23:28,956 --> 00:23:33,470
the end result is, 2N minus two choose N 
minus one. 

282
00:23:33,470 --> 00:23:39,048
And very much the same calculations. 
Just with a slightly different result. 

283
00:23:39,048 --> 00:23:44,917
that's accumulated cost and then the 
final thing is to divide those two 

284
00:23:44,917 --> 00:23:49,264
and if you divide those two almost 
everything cancels. 

285
00:23:49,264 --> 00:23:52,741
except for an N plus one times NN on the 
top. 

286
00:23:52,741 --> 00:23:58,175
2N times 2N minus one on the bottom. 
so that's three N's and two N's and 

287
00:23:58,175 --> 00:24:02,740
that's an asymptotic 2N over four. 
So about a quarter of the. 

288
00:24:02,740 --> 00:24:09,070
[COUGH] Nodes in a random binary tree are 
leaves. 

289
00:24:09,070 --> 00:24:14,760
[COUGH], and that's an example of the use 
of 

290
00:24:14,760 --> 00:24:20,829
Accumulated generating functions to 
discover the average cost of a, of a 

291
00:24:20,829 --> 00:24:24,277
quantity. 
And we'll be seeing lots and lots of 

292
00:24:24,277 --> 00:24:31,021
derivations like this and actually many 
of'em will be much simpler because we 

293
00:24:31,021 --> 00:24:37,391
have coherent ways to deal with 
explaining the decomposition in terms of 

294
00:24:37,391 --> 00:24:42,187
the generating function. 
and we'll talk about that when we 

295
00:24:42,187 --> 00:24:47,158
introduce analytic combinatorics. 
So that's counting with generating 

296
00:24:47,158 --> 00:24:50,300
functions. 
And so now I want to finish by 

297
00:24:50,300 --> 00:24:55,369
Giving you a few exercises that you might 
do before the next lecture. 

298
00:24:55,369 --> 00:25:00,777
so the first one is to just practice 
solving an recurrence, and this is an 

299
00:25:00,777 --> 00:25:04,900
example that shows that the initial 
conditions really matter. 

300
00:25:04,900 --> 00:25:09,902
So solve recurrence with one set of 
initial conditions, and then solve the 

301
00:25:09,902 --> 00:25:14,228
same recurrence with just that one 
initial condition changed. 

302
00:25:14,228 --> 00:25:17,878
and you can see the impact of just that 
one change. 

303
00:25:17,878 --> 00:25:22,812
on the recurrence and also get some 
practice on sovereign recurrences. 

304
00:25:22,812 --> 00:25:27,424
another thing that You might do is 
practice expanding some unknown 

305
00:25:27,424 --> 00:25:31,395
generating functions. 
And there's many exercises like this in 

306
00:25:31,395 --> 00:25:34,910
the book. 
these are just a couple that you might 

307
00:25:34,910 --> 00:25:37,839
try. 
So what about one over square root of 

308
00:25:37,839 --> 00:25:40,607
1-Z? 
natural log of one over one - z. 

309
00:25:40,607 --> 00:25:46,358
There's a bunch of ways to do that 
there's a hint or one way that might 

310
00:25:46,358 --> 00:25:49,972
work. 
that'll give you some practice in how we 

311
00:25:49,972 --> 00:25:53,438
extract coefficients from generating 
functions. 

312
00:25:53,438 --> 00:25:57,420
And you can try some other exercises 
there as well. 

313
00:25:57,420 --> 00:26:03,496
So, what I, think would be useful, for 
people to do to, make sure they 

314
00:26:03,496 --> 00:26:10,111
understood the material in this lecture. 
one thing is to, if you've got access to 

315
00:26:10,111 --> 00:26:15,725
a symbolic math, math system, [COUGH] or 
if you're used to using one. 

316
00:26:15,725 --> 00:26:20,110
do things like, check the initial values 
on that 

317
00:26:20,110 --> 00:26:25,240
Equation that we got for accumulated 
costs for leaves in binary trees. 

318
00:26:25,240 --> 00:26:31,031
Similar to the check that I did just that 
the regular Catalan recurrence holds. 

319
00:26:31,031 --> 00:26:36,748
And if you don't have a symbolic math 
system, look around to see if you can do 

320
00:26:36,748 --> 00:26:39,900
that in some way. 
Some are freely available. 

321
00:26:39,900 --> 00:26:47,049
I think again the best way to learn this 
material is after you've listened to the 

322
00:26:47,049 --> 00:26:53,439
lecture and got some idea of the overview 
of the material is to read the text 

323
00:26:53,439 --> 00:26:59,295
carefully.'Cause the text really does 
tell the story in, in some detail. 

324
00:26:59,295 --> 00:27:06,369
and then it's certainly worth while to 
check your understanding by really try to 

325
00:27:06,369 --> 00:27:09,640
write up full solutions to those 
exercises. 

326
00:27:09,640 --> 00:27:13,900
maybe using TEC. 
Or, or maybe using HTML plus 

327
00:27:13,900 --> 00:27:19,799
Jack and really seeing that you can 
create the math that is the solution to 

328
00:27:19,799 --> 00:27:23,783
those exercises. 
That's an introduction to generating 

329
00:27:23,783 --> 00:27:24,560
functions.