1
00:00:03,300 --> 00:00:09,206
As a poster child for the application of 
generating functions next we're going to 

2
00:00:09,206 --> 00:00:14,969
take a look at the Catalan numbers, which 
are a fundamental sequence of great 

3
00:00:14,969 --> 00:00:19,939
interest in combinatorics. 
one way to, there's many applications of 

4
00:00:19,939 --> 00:00:25,558
the Catalan numbers, and I'll give a few. 
So one of the earliest that people 

5
00:00:25,558 --> 00:00:31,105
thought about was, how many different 
ways are there to take a polygon with n+2 

6
00:00:31,105 --> 00:00:37,300
sides and draw lines from one vertex to 
another and make it all triangles? 

7
00:00:37,300 --> 00:00:42,114
So for example if you have a pentagon, 
you have all these different ways to 

8
00:00:42,114 --> 00:00:47,854
triangulate it well actually it's easy 
just draw from any vertex you draw to the 

9
00:00:47,854 --> 00:00:52,977
two opposite and in a five vertices you 
get five triangulations or if it's a 

10
00:00:52,977 --> 00:00:57,421
square you just get two but if you, if 
it's a hexagon, there's lots of 

11
00:00:57,421 --> 00:01:03,038
possibilities you can do three like that 
or you can do these N shapes and there's 

12
00:01:03,038 --> 00:01:08,957
lots of possibilities and actually turns 
out that the number of triangulations of 

13
00:01:08,957 --> 00:01:17,009
a hexagon is fourteen. 
so that's a number sequence that is 

14
00:01:17,009 --> 00:01:21,919
described by this recurrence relation, 
over here. 

15
00:01:21,919 --> 00:01:27,340
the in, in general if we draw and leave 
K. 

16
00:01:27,340 --> 00:01:33,691
we draw our diagnol and leave K vertices 
on one side, and N minus one minus K on 

17
00:01:33,691 --> 00:01:38,686
the other side, and there's one less 
because we draw the triangle, then you 

18
00:01:38,686 --> 00:01:44,467
can triangulate those anyway that you 
want and each one of them independently. 

19
00:01:44,467 --> 00:01:49,177
So it says thatt the number of 
triangulations has to satisfy that 

20
00:01:49,177 --> 00:01:54,244
reccurence relation, sum from zero to K 
less than N, T, K, T, N minus one, K, 

21
00:01:54,244 --> 00:01:58,740
plus an extra because there's always one 
way to triangulate the 

22
00:01:58,740 --> 00:02:03,997
the triangle. 
So that's a recurrence relation that 

23
00:02:03,997 --> 00:02:09,031
we're going to take a look at solving. 
but it applies in many other 

24
00:02:09,031 --> 00:02:13,346
applications. 
here's another application the so called, 

25
00:02:13,346 --> 00:02:16,708
gambler's ruin problem. 
So you're a gambler, 

26
00:02:16,708 --> 00:02:20,979
you start with zero dollars and you make 
$1 bets. 

27
00:02:20,979 --> 00:02:26,959
And if you win, the line goes up. 
There's just a graph of the amount of 

28
00:02:26,959 --> 00:02:31,487
money that you have. 
So in this case, there's two wins, 

29
00:02:31,487 --> 00:02:36,356
followed by a loss. 
Win, loss, win, loss, two wins and then a 

30
00:02:36,356 --> 00:02:40,969
bunch of losses. 
And the idea is the gambler will keep 

31
00:02:40,969 --> 00:02:47,035
going until having $0 makes a bet and 
loses and then the game's over. 

32
00:02:47,035 --> 00:02:53,779
And how many different A's so are there 
for, for, the for, for the gambler to do 

33
00:02:53,779 --> 00:02:59,588
that, I would say N, N wins in the 
sequence and a lot of b loses to and so, 

34
00:02:59,588 --> 00:03:05,397
and again, if you try out all the 
possibilities it turns out that, there's 

35
00:03:05,397 --> 00:03:11,059
only two possibilities, if there's two 
dollars you could win, lose, win, lose or 

36
00:03:11,059 --> 00:03:16,941
you can win 2 and then lose 3 and those 
are the only two possibilities. 

37
00:03:16,941 --> 00:03:22,530
And there's five different ways for three 
wins in fourteen for four wins. 

38
00:03:22,530 --> 00:03:27,037
And same sequence because it satisfies 
the same recurrence. 

39
00:03:27,037 --> 00:03:32,794
You can just set up the recurrence by the 
first time the gambler gets back to zero 

40
00:03:32,794 --> 00:03:37,787
if that happens after K wins. 
then independently you have a gambler's 

41
00:03:37,787 --> 00:03:42,850
ruin problem on K and then N minus 1K. 
And it follows the same recurrence. 

42
00:03:42,850 --> 00:03:46,885
U, here's another one binary tree 
structures. 

43
00:03:46,885 --> 00:03:54,526
So a binary tree is a root node that has 
connected to two binary trees, the tree 

44
00:03:54,526 --> 00:03:59,850
on the left and the tree on the right or 
it could be empty. 

45
00:03:59,850 --> 00:04:05,367
w-, that's called an external node. 
So how many different binary trees are 

46
00:04:05,367 --> 00:04:09,347
there with N nodes? 
And we'll look in much m-, in a lot of 

47
00:04:09,347 --> 00:04:12,630
detail at binary trees later one. 
So this f-, 

48
00:04:12,630 --> 00:04:17,742
Two different binary trees with two nodes 
so that is you got one of the root and 

49
00:04:17,742 --> 00:04:22,561
you could have a one node tree on the 
left or a one node tree on the right and 

50
00:04:22,561 --> 00:04:27,321
every node has to have two children and 
the ones at the bottom have two blank 

51
00:04:27,321 --> 00:04:29,731
children, those are called external 
nodes. 

52
00:04:29,731 --> 00:04:34,667
For three, there's five possibilities you 
have a node at the root and it could be 

53
00:04:34,667 --> 00:04:39,192
empty on the right with either one of 
these trees on the left or it could be 

54
00:04:39,192 --> 00:04:43,600
empty on the left with either one of 
these trees on the right or you could 

55
00:04:43,600 --> 00:04:46,480
have two trees of size one, one on either 
side. 

56
00:04:46,480 --> 00:04:49,592
so there's five possibilities for three 
nodes. 

57
00:04:49,592 --> 00:04:53,593
And similarly, there's fourteen 
possibilities for four nodes. 

58
00:04:53,593 --> 00:04:59,246
so, you could have empty on the left, and 
anyone of the three node trees empty on 

59
00:04:59,246 --> 00:05:02,295
the right. 
Anyone of the three node trees on the 

60
00:05:02,295 --> 00:05:05,026
left. 
Empty on the left, anyone of the three 

61
00:05:05,026 --> 00:05:09,408
node trees on the right. 
or you could have one on one side and two 

62
00:05:09,408 --> 00:05:14,906
on the other side in four possible ways. 
so again, same number sequence again, 

63
00:05:14,906 --> 00:05:20,440
satisfies the same recurrence. 
if you got k nodes on the left, you are 

64
00:05:20,440 --> 00:05:23,987
going to have n minus one minus k nodes 
on the right. 

65
00:05:23,987 --> 00:05:29,378
And you can try all possibilities on 
either side so it's got to satisfy the 

66
00:05:29,378 --> 00:05:34,770
recurrence, where you, T equals n is 
equal to the sum for all k up to n minus 

67
00:05:34,770 --> 00:05:40,020
one of Tk, Tn minus one minus k plus 
delta trying to make it true for zero, 

68
00:05:40,020 --> 00:05:43,035
Catalan numbers. 
here's another one. 

69
00:05:43,035 --> 00:05:49,305
How many trees with n nodes? 
A tree is a node connected to a forest of 

70
00:05:49,305 --> 00:05:52,559
trees. 
To any number of trees, so it's not 

71
00:05:52,559 --> 00:05:58,273
restricted to be just two. 
And again, we'll talk in detail later in 

72
00:05:58,273 --> 00:06:01,686
the course. 
about trees and binary trees. 

73
00:06:01,686 --> 00:06:06,606
but for now, I just want to point out all 
the possibilities. 

74
00:06:06,606 --> 00:06:12,952
and it satisfies these same recurrents. 
so Catalan numbers describe a lot of 

75
00:06:12,952 --> 00:06:18,207
combinatorial objects of interest. 
So how are we going to solve the Catalan 

76
00:06:18,207 --> 00:06:23,111
recurrence with generating functions? 
Well, we're going to use the formula. 

77
00:06:23,111 --> 00:06:26,334
we got the recurrence that holds for all 
N. 

78
00:06:26,334 --> 00:06:32,220
now we're going to, what's the next step? 
It's multiply by Z to the N and sum on N. 

79
00:06:32,220 --> 00:06:35,314
on the left hand side, that gives us T of 
z. 

80
00:06:35,314 --> 00:06:39,686
that's the generating function for the 
Catalan numbers. 

81
00:06:39,686 --> 00:06:44,663
On the right hand side we'll get a one 
for the delta term on the right. 

82
00:06:44,663 --> 00:06:50,381
and then we get some [INAUDIBLE] zero. 
Zero less than or equal to K less than N, 

83
00:06:50,381 --> 00:06:54,585
TKTN - 1. 
and that looks familiar, it is familiar. 

84
00:06:54,585 --> 00:06:58,065
that's 
we're going to work backwards from the 

85
00:06:58,065 --> 00:07:01,048
convolution derivation that we did 
before. 

86
00:07:01,048 --> 00:07:04,457
so, 
Now what we'll do is, first thing we'll 

87
00:07:04,457 --> 00:07:09,572
do is switch order of summation. 
so switching order summation means if 

88
00:07:09,572 --> 00:07:15,050
you're try for every value of K then the 
inner sum is just for N bigger than K. 

89
00:07:15,050 --> 00:07:22,520
now in that inner sum will change N to N 
plus K plus one. 

90
00:07:22,520 --> 00:07:28,275
Change n to n+k+1, n bigger than k, 
that's n bigger than or equal to k+1. 

91
00:07:28,275 --> 00:07:32,260
So that's the same as n bigger equal to 
zero. 

92
00:07:32,260 --> 00:07:36,333
And then the t sub n-1-k just becomes T 
sub N. 

93
00:07:36,333 --> 00:07:41,646
And then we have z^(n+k+1). 
And that gives us a way to split it into 

94
00:07:41,646 --> 00:07:46,162
independent sums by distributing the ks 
and the ns. 

95
00:07:46,162 --> 00:07:53,309
And then you can see immediately the one 
z comes out and then it's two copies of 

96
00:07:53,309 --> 00:07:59,838
the generating function t of z. 
so that's a backwards convolution that 

97
00:07:59,838 --> 00:08:06,798
shows us that the Catalan generating 
function has to satisfy this functional 

98
00:08:06,798 --> 00:08:10,836
equation. 
T of c equals one plus z times t of z 

99
00:08:10,836 --> 00:08:13,499
squared. 
So we're halfway there. 

100
00:08:13,499 --> 00:08:19,600
we've got a, an equation that the 
generating function has to satisfy. 

101
00:08:19,600 --> 00:08:24,183
Now I. 
Common sense rule for working with 

102
00:08:24,183 --> 00:08:30,238
generating functions that I want to point 
out, and again it's always worth while to 

103
00:08:30,238 --> 00:08:35,861
check your math with your computer, and 
that includes symbolic, calculations, 

104
00:08:35,861 --> 00:08:40,042
like this one, 
You know the initial values of T of Z, we 

105
00:08:40,042 --> 00:08:46,458
did the, we did the examples so we know 
that it starts out being one plus Z, plus 

106
00:08:46,458 --> 00:08:52,259
2Z squared plus 5Z cubed plus 14Z four. 
before we go any further we might want to 

107
00:08:52,259 --> 00:08:58,239
check that this equation that we have are 
really holds and you can do it in pencil 

108
00:08:58,239 --> 00:09:04,079
and paper or you can use a symbolic maths 
system and you could see that if you take 

109
00:09:04,079 --> 00:09:09,850
1 + z times 1 + z^2 and so forth I just 
took it out to four terms here the ones 

110
00:09:09,850 --> 00:09:16,386
that we know if we multiply them out it 
the you get 1 +z+2z z +2z^2 + 5z^3 + 4 

111
00:09:16,386 --> 00:09:20,071
and so forth. 
Now after a while the terms are no good 

112
00:09:20,071 --> 00:09:23,270
because we didn't take these terms far 
enough. 

113
00:09:23,270 --> 00:09:28,773
but still that gives confidence and 
actually you can boot strap this to get 

114
00:09:28,773 --> 00:09:32,075
more terms. 
But, it gives confidence that we've got 

115
00:09:32,075 --> 00:09:36,731
the right equation. 
so that's just checking your math with 

116
00:09:36,731 --> 00:09:42,857
the computer even when it's, symbolic. 
Alright so now what we need to do is to 

117
00:09:42,857 --> 00:09:48,648
extract coefficients to find an 
expression for the N-th Catalan number. 

118
00:09:48,648 --> 00:09:55,048
So that's the GF equation well it's an 
equation we know how to solve with the 

119
00:09:55,048 --> 00:10:00,681
quadratic formula. 
and so that's the solution with the 

120
00:10:00,681 --> 00:10:07,073
quadratic formula. 
just implying the eighth grade formula. 

121
00:10:07,073 --> 00:10:13,770
and then, we have to pick 1 plus or 1 
minus and 

122
00:10:13,770 --> 00:10:19,900
It, it's going to be the minus. 
So just left out that one consideration. 

123
00:10:19,900 --> 00:10:24,236
and that you get from checking with the 
initial values. 

124
00:10:24,236 --> 00:10:30,141
so now how do we deal with that? 
We, we expand one over, square root of 1 

125
00:10:30,141 --> 00:10:36,645
- 4Z with, just use the binomial theorem. 
It's 1 - 4Z to the one-half power, so 

126
00:10:36,645 --> 00:10:40,010
it's the sum of one-half 2's and 4Z to 
the N. 

127
00:10:40,010 --> 00:10:46,845
and then this one part goes away. 
and so, and again, we can check that from 

128
00:10:46,845 --> 00:10:52,043
initial values. 
so that's a key step for this generating 

129
00:10:52,043 --> 00:10:55,057
function. 
We have a solution that uses the 

130
00:10:55,057 --> 00:10:59,434
quadratic formula. 
And then we have a [COUGH] an expansion 

131
00:10:59,434 --> 00:11:04,530
of a function that we know how to expand, 
know how to find coefficients. 

132
00:11:04,530 --> 00:11:10,021
so that tells us what T sub N is. 
it's minus a half. 

133
00:11:10,021 --> 00:11:13,945
One half choose N plus one minus four to 
the N plus one. 

134
00:11:13,945 --> 00:11:17,800
This extra Z is what gives to, leads the, 
the N plus one. 

135
00:11:17,800 --> 00:11:24,024
Now that is, it is okay, it is not 
totally satisfying because the one half 

136
00:11:24,024 --> 00:11:30,761
n+1 is may be not such familiar function 
in its way to manipulate this to get it 

137
00:11:30,761 --> 00:11:37,583
to be a little more familiar function and 
actually next time we will talk about 

138
00:11:37,583 --> 00:11:43,466
much better way to continue to manipulate 
it to get really a concise 

139
00:11:43,466 --> 00:11:48,242
representation. 
But let us just do a little more algebra 

140
00:11:48,242 --> 00:11:52,872
to get the. 
It's in more of a form that we can people 

141
00:11:52,872 --> 00:11:56,950
can. 
relate to so 

142
00:11:56,950 --> 00:12:01,913
This is the definition of the binomial 
coefficient, when the upper index. 

143
00:12:01,913 --> 00:12:05,429
for any binomial coefficient we just, 
it's 

144
00:12:05,429 --> 00:12:10,876
On the bottom is N plus one factorial. 
And on the top is N plus one terms, where 

145
00:12:10,876 --> 00:12:13,978
we subtract zero, one, two, all the way 
up to N. 

146
00:12:13,978 --> 00:12:20,459
so that's just the do, definition. 
And there's the - 1/2 and there's the - 4 

147
00:12:20,459 --> 00:12:24,464
to the N + 1. 
And so now what we're going to do is take 

148
00:12:24,464 --> 00:12:29,927
we have N plus one terms here and we've 
got n plus one force and we're going to 

149
00:12:29,927 --> 00:12:35,916
take a bunch of those if we'll take the n 
plus one minus 2's and multiply them in, 

150
00:12:35,916 --> 00:12:41,248
and one of them kills that and then the 
others you get one, three, five all the 

151
00:12:41,248 --> 00:12:47,093
way up to 2n minus one like that. 
so that's a slight trick but cleans it up 

152
00:12:47,093 --> 00:12:54,133
quite a bit and now if you have that then 
if you fill in the evens so two to the n 

153
00:12:54,133 --> 00:12:58,112
is two over one times four over two and 
so forth. 

154
00:12:58,112 --> 00:13:05,229
As now we have the odds and the evens and 
we have an n factorial so that's going to 

155
00:13:05,229 --> 00:13:11,351
immediately give us 2n factorial over n 
factorial times n factorial which is 2n 

156
00:13:11,351 --> 00:13:15,159
choose n. 
So that's a proof that the number of 

157
00:13:15,159 --> 00:13:20,851
binary trees in N nodes, number of 
general trees in N nodes, the number of 

158
00:13:20,851 --> 00:13:24,671
ways to triangulate an N plus 2-gon, and 
so forth. 

159
00:13:24,671 --> 00:13:31,533
The Catalan numbers is one over N plus 
one, times two N choose N, and that's one 

160
00:13:31,533 --> 00:13:36,134
of the most famous number sequences in 
combinatorics. 

161
00:13:36,134 --> 00:13:43,230
and we'll see in many cases we explicitly 
use data structures like trees in 

162
00:13:43,230 --> 00:13:48,628
practical algorithms and data structures. 
So we need to understand these properties 

163
00:13:48,628 --> 00:13:52,017
of them. 
and we're going to continue working with 

164
00:13:52,017 --> 00:13:56,600
the Catalan numbers in several other 
occasions later on in the course.