1
00:00:00,012 --> 00:00:06,054
Now we're ready to talk about really what 
is analytic combinatorics. 

2
00:00:06,054 --> 00:00:13,210
So it's a calculus for the quantitative 
study of large combinatorial structures. 

3
00:00:13,210 --> 00:00:19,227
And generating functions are the central 
object of study in analytic 

4
00:00:19,227 --> 00:00:23,881
combinatorics. 
So the basic process is 3 step Pretty 

5
00:00:23,881 --> 00:00:27,709
simple. 
first thing we do is define what's called 

6
00:00:27,709 --> 00:00:33,016
a combinatorial construction that per, 
precisely specifies the structure that 

7
00:00:33,016 --> 00:00:36,770
you want to study. 
the second thing we do is use what's 

8
00:00:36,770 --> 00:00:41,856
called a transfer theorem, a symbolic 
transfer theorem, to get a generating 

9
00:00:41,856 --> 00:00:46,497
function equation. 
And then we use another analytic transfer 

10
00:00:46,497 --> 00:00:50,764
theorem to extract the asymptotics of the 
coefficient. 

11
00:00:50,764 --> 00:00:52,942
That's it. 
A 3 step process. 

12
00:00:52,942 --> 00:00:58,896
And what's important is that it's very 
often the case, that all 3 steps are 

13
00:00:58,896 --> 00:01:02,844
almost immediate. 
For example, for our binary tree 

14
00:01:02,844 --> 00:01:09,232
question, how many binary trees are there 
with N nodes? With analytic combinatorics 

15
00:01:09,232 --> 00:01:12,254
we write down the combinatorial 
instruction. 

16
00:01:12,254 --> 00:01:17,326
That's a formula like that one and I'll 
talk on the next slide where that comes 

17
00:01:17,326 --> 00:01:19,814
from. 
Then we use a transfer theorem. 

18
00:01:19,814 --> 00:01:25,007
A simple, this one simple to approve and 
simple to apply that immediately gives 

19
00:01:25,007 --> 00:01:30,373
the generating function equation. 
it's the same one that we got, the hard 

20
00:01:30,373 --> 00:01:33,817
way before. 
And then we use an analytic transfer 

21
00:01:33,817 --> 00:01:38,332
theorem that immediately gives us the 
coefficient asymptotics. 

22
00:01:38,332 --> 00:01:43,749
And again this theorem is very 
sophisticated to prove but it's easy to 

23
00:01:43,749 --> 00:01:47,634
apply. 
so a three step process to solve the same 

24
00:01:47,634 --> 00:01:53,210
problem, avoiding all of the detail. 
That's what analytic combinatorics can do 

25
00:01:53,210 --> 00:01:56,778
for us. 
Let's look at these three steps, in 

26
00:01:56,778 --> 00:02:00,149
detail. 
So, the first step, is to specify the 

27
00:02:00,149 --> 00:02:06,259
class using a combinatorial construction; 
and these things are built from natural 

28
00:02:06,259 --> 00:02:12,978
operations and once you've, 
see a few of these in, in simple examples 

29
00:02:12,978 --> 00:02:19,404
and you'll see how natural they are. 
they're algebraic formulas that are built 

30
00:02:19,404 --> 00:02:25,601
with combinatorial operators and the 
operands are either atoms, or the basic 

31
00:02:25,601 --> 00:02:28,739
building blocks, like nodes in a binary 
tree. 

32
00:02:28,739 --> 00:02:32,914
or they could be other constructions or, 
or classes. 

33
00:02:32,914 --> 00:02:38,885
and there's two cases that I won't get 
into that much detail on in this talk, 

34
00:02:38,885 --> 00:02:44,680
but either the atoms are unlabeled, there 
are no difference between them, or 

35
00:02:44,680 --> 00:02:51,877
they're all different they're labeled. 
in, in That leads to, differences in the, 

36
00:02:51,877 --> 00:02:57,886
in the operators, and in the unlabeled 
case we use ordinary generating functions 

37
00:02:57,886 --> 00:03:03,890
and in label we use exponential. 
but, at this level, there's not Not much 

38
00:03:03,890 --> 00:03:07,545
different. 
and the idea is that what we're doing is 

39
00:03:07,545 --> 00:03:11,174
very similar to formal languages in 
computer science. 

40
00:03:11,174 --> 00:03:16,606
but the idea of a combinatorial 
construction, we are particularly paying 

41
00:03:16,606 --> 00:03:22,037
particular attention to ambiguity if 
you're familiar with formal languages. 

42
00:03:22,037 --> 00:03:27,693
and so, there's a lot of constructions, 
but the basic ones that I could use to 

43
00:03:27,693 --> 00:03:32,778
illustrate one analytic combinatorics is 
are very simple. 

44
00:03:32,778 --> 00:03:35,751
so there's a union operation, so A= B + 
C. 

45
00:03:35,751 --> 00:03:40,830
and the letters just represent classes of 
combinatorial objects. 

46
00:03:40,830 --> 00:03:45,992
A combinatorial class is a set of objects 
and the size function is all. 

47
00:03:45,992 --> 00:03:49,711
there's a Cartesian product, which is 
pairs. 

48
00:03:49,711 --> 00:03:56,443
and there's a Sequence, which is a 
sequence of a just shorthand for pairs, 

49
00:03:56,443 --> 00:04:01,984
any number of pairs. 
so this is the basic constructions that 

50
00:04:01,984 --> 00:04:09,581
we can use and for example this is just a 
fully formal bases for being able to 

51
00:04:09,581 --> 00:04:17,074
write down a specification of what is a 
binary tree with that formula, t = e 

52
00:04:17,074 --> 00:04:23,843
which is the empty class + z which is a 
class containing one thing which is a 

53
00:04:23,843 --> 00:04:28,774
node. 
[COUGH] That, is a product with a node, a 

54
00:04:28,774 --> 00:04:34,863
tree is a sequence of a node and 2 trees. 
so that's a formula that fully specifies 

55
00:04:34,863 --> 00:04:39,718
what we mean by binary tree. 
And we define a binary tree in English, 

56
00:04:39,718 --> 00:04:44,652
we usually say, a binary tree is empty or 
a node and 2 binary trees. 

57
00:04:44,652 --> 00:04:47,875
This is saying that formally in math 
speak. 

58
00:04:47,875 --> 00:04:50,741
That's what a combinatorial construction 
is. 

59
00:04:50,741 --> 00:04:55,344
You'll see lots of examples of 
combinatorial constructions later on. 

60
00:04:55,344 --> 00:04:59,412
So then, the next thing is to introduce 
generating functions. 

61
00:04:59,412 --> 00:05:04,487
Well, one of the things about the 
combinatorial constructions that we use, 

62
00:05:04,487 --> 00:05:09,962
is that we associate the constructions 
with operations on generating functions. 

63
00:05:09,962 --> 00:05:15,762
So, this part happens immediately. 
So for unlabeled classes, we use ordinary 

64
00:05:15,762 --> 00:05:19,237
generating functions, and it's the same 
as before. 

65
00:05:19,237 --> 00:05:25,397
we sum for all sizes, the number of 
objects of a given size times Z ^ N, 

66
00:05:25,397 --> 00:05:31,542
where Z is a synthetic variable. 
And, by the way, that's exactly equal to 

67
00:05:31,542 --> 00:05:36,382
summing over every tree. 
Z to its size, as for all the trees of 

68
00:05:36,382 --> 00:05:40,047
size N, there's one term, and that gives 
T sub N. 

69
00:05:40,047 --> 00:05:46,982
and that representation of the generating 
function, is what gives easy proof of the 

70
00:05:46,982 --> 00:05:51,553
transfer theorem. 
So although I won't take time To do the 

71
00:05:51,553 --> 00:05:56,243
proofs right now. 
So, the basic transfer theorems are very 

72
00:05:56,243 --> 00:06:00,100
simple. 
If you've got 2 classes b and c, and you 

73
00:06:00,100 --> 00:06:05,180
take the union, the generating function 
for the result, is the sum of the 

74
00:06:05,180 --> 00:06:11,207
generating function's of the 2 offering. 
If you do the Cartesian product, it's the 

75
00:06:11,207 --> 00:06:14,992
product. 
If you do the sequence, it's one over one 

76
00:06:14,992 --> 00:06:18,497
minus. 
And that just comes from sum of one plus 

77
00:06:18,497 --> 00:06:22,537
B(z) plus B(z) squared plus B(z) cubed, 
and so forth. 

78
00:06:22,537 --> 00:06:28,967
That easy to prove from the product. 
so, given the operations we immediately 

79
00:06:28,967 --> 00:06:32,258
have a translation to generating 
functions. 

80
00:06:32,258 --> 00:06:37,742
So for example, for binary trees, our 
combinatorial class is the set of all 

81
00:06:37,742 --> 00:06:41,834
trees. 
And the size function is absolute of t, 

82
00:06:41,834 --> 00:06:47,441
notation, is the number of nodes in t. 
so the, what we're interested in is the 

83
00:06:47,441 --> 00:06:51,104
counting sequence, the number of trees 
with N nodes. 

84
00:06:51,104 --> 00:06:57,637
and from this very basic information, Why 
we have the construction that I showed on 

85
00:06:57,637 --> 00:07:03,249
the last slide, immediately translates to 
a generating function equation. 

86
00:07:03,249 --> 00:07:07,691
the empty class generating function for 
that is 1 z. 

87
00:07:07,691 --> 00:07:13,021
The generating function for class 
consisting of a single node is just z. 

88
00:07:13,021 --> 00:07:17,712
and then there's t of z twice so it's z * 
t of z ^. 

89
00:07:17,712 --> 00:07:22,965
So that's a fully rigorous mathematical 
transfer from a construction to a gf 

90
00:07:22,965 --> 00:07:26,986
equation. 
we had many other constructions but for 

91
00:07:26,986 --> 00:07:30,497
all of them there's associated transfer 
theorems. 

92
00:07:30,497 --> 00:07:35,852
nowadays that's what we mean by a 
combinatorial construction, that's one 

93
00:07:35,852 --> 00:07:38,842
for which we know a good transfer 
theorem. 

94
00:07:38,842 --> 00:07:43,898
So generating functions are the key to 
analytic combinatorics. 

95
00:07:43,898 --> 00:07:50,083
But I have to point out quickly that the 
use of generating functions within 

96
00:07:50,083 --> 00:07:54,288
combinatorics was very controversial for 
some time. 

97
00:07:54,288 --> 00:08:00,372
For example, here's a quote from Claude 
Berge, a French mathematician. 

98
00:08:00,372 --> 00:08:04,793
and expressed the point of view of many 
people working in combinatorial 

99
00:08:04,793 --> 00:08:08,261
mathematics. 
So the property is understood better when 

100
00:08:08,261 --> 00:08:13,510
one constructs a bijection, then when one 
calculates the coffeients of a polynomial 

101
00:08:13,510 --> 00:08:16,282
whos variables have no particular 
meaning. 

102
00:08:16,282 --> 00:08:21,471
The method of generating functions, which 
has had devastating effects for a 

103
00:08:21,471 --> 00:08:25,293
century, has fallen into obsolescence for 
this reason. 

104
00:08:25,293 --> 00:08:30,330
That was Berge's point of view. 
Flajolet had a completely different point 

105
00:08:30,330 --> 00:08:33,645
of view. 
He says that they are really the central 

106
00:08:33,645 --> 00:08:39,137
objects of the theory not a mere artifact 
to solve recurrences, as is still often 

107
00:08:39,137 --> 00:08:43,919
believed, and we'll see why. 
When we get to the next step of analytic 

108
00:08:43,919 --> 00:08:47,361
combinatorics. 
What we're going to do is use view the 

109
00:08:47,361 --> 00:08:51,411
generating function. 
It's still a synthetic variable, but 

110
00:08:51,411 --> 00:08:54,473
we're going to view it as a complex 
variable. 

111
00:08:54,473 --> 00:08:59,585
So, the generating function is going to 
be a function in the complex plane. 

112
00:08:59,585 --> 00:09:04,521
And that viewpoint allows us to unlock 
analytic transfer theorems, that 

113
00:09:04,521 --> 00:09:08,032
immediately give us the coefficient 
asymptotics. 

114
00:09:08,032 --> 00:09:15,241
So, for example, even real analysis, but 
also in complex analysis, the coefficient 

115
00:09:15,241 --> 00:09:21,301
of z to the n and 1 over 1 minus z over 
row, that's got a pull, row, it's row to 

116
00:09:21,301 --> 00:09:25,222
the minus n, sum of z to the n row to the 
minus n. 

117
00:09:25,222 --> 00:09:32,144
so that's easy. 
but, we can do much, much more, so for 

118
00:09:32,144 --> 00:09:40,036
example, if we take 1 -0 to the alpha, 
were alpha is any real, except it can't 

119
00:09:40,036 --> 00:09:44,901
be any negative integer, it degenerates 
in that case. 

120
00:09:44,901 --> 00:09:51,259
It's asymptotic to 
N^(alpha-1)/gamma(alpha), that's the 

121
00:09:51,259 --> 00:09:56,711
gamma function which generalizes the 
factorial rho^-N. 

122
00:09:56,711 --> 00:10:05,319
and even if there are logarithmic factors 
we can prove the transfer theorem that 

123
00:10:05,319 --> 00:10:11,023
coefficient is Z^N. 
And that function throws out a log N 

124
00:10:11,023 --> 00:10:14,381
factor. 
now these are simple to apply. 

125
00:10:14,381 --> 00:10:19,614
they couldn't look simpler. 
the proof of them is extremely 

126
00:10:19,614 --> 00:10:23,736
sophisticated. 
And really, it was publication of this 

127
00:10:23,736 --> 00:10:29,952
paper, by Philippe and Andrew Odlyzko, in 
1990, it was really a watershed moment. 

128
00:10:29,952 --> 00:10:36,342
before that time we suspected that we 
could get these answers out in this way, 

129
00:10:36,342 --> 00:10:39,902
but proving it was another A thing 
entirely. 

130
00:10:39,902 --> 00:10:44,951
that's what I said, when I said, we 
needed to, needed to do the math. 

131
00:10:44,951 --> 00:10:49,257
And Philippe and Andrew [INAUDIBLE] 
definitely did the math. 

132
00:10:49,257 --> 00:10:55,813
it's worth understanding, this paper, but 
it's truly tour-de-force and a, and a 

133
00:10:55,813 --> 00:10:59,436
masterpiece. 
but now, we can benefit from, 

134
00:10:59,436 --> 00:11:03,762
There's a very, long list of transfer 
theorems, of this type. 

135
00:11:03,762 --> 00:11:07,240
it's really starting with, with this 
basic one. 

136
00:11:07,240 --> 00:11:11,484
And these things are effective, even for 
approximations and near the 

137
00:11:11,484 --> 00:11:14,462
singularities. 
When there's other functions. 

138
00:11:14,462 --> 00:11:19,668
Functions involved. 
but, for example, for our problem, if you 

139
00:11:19,668 --> 00:11:25,220
want the coefficient of Z ^ N in square 
root of 1 - 4Z, you just plug in the 

140
00:11:25,220 --> 00:11:28,897
standard scale equation, alpha = -1/2 
Half. 

141
00:11:28,897 --> 00:11:35,747
and, row =, 1/4. 
and immediately, you get the asymptotics 

142
00:11:35,747 --> 00:11:41,372
of the coefficient. 
it's asymptotic to n to the - 3 halves 

143
00:11:41,372 --> 00:11:47,542
over gamma -1/2 4 to the n. 
and gamma - 1/2 is - 1/2 square root of 

144
00:11:47,542 --> 00:11:49,912
pi. 
And that, boom. 

145
00:11:49,912 --> 00:11:54,773
That gives us the asymptotics, 
immediately just directly applying the 

146
00:11:54,773 --> 00:12:01,008
theorem without worrying about all the 
sophistication under, under, underlying 

147
00:12:01,008 --> 00:12:03,393
its proof. 
So that's the third step. 

148
00:12:03,393 --> 00:12:07,221
So there you are. 
That's two different ways to count binary 

149
00:12:07,221 --> 00:12:10,398
trees. 
You can go through the classical analyses 

150
00:12:10,398 --> 00:12:15,538
of algorithms all those steps. 
Which, by the way a lot of students and 

151
00:12:15,538 --> 00:12:20,649
I'd say even a lot of professors might 
take quite awhile to really get through 

152
00:12:20,649 --> 00:12:24,081
all the steps to do this Catalan number 
derivation. 

153
00:12:24,081 --> 00:12:29,390
But with analytic combinatorics, it's 
boom, boom, boom, there's the answer, 4 

154
00:12:29,390 --> 00:12:33,610
to the n over square root of pi n cubed. 
take your pick. 

155
00:12:33,610 --> 00:12:40,426
most modern researchers, who are looking 
at scientific study of large quantitative 

156
00:12:40,426 --> 00:12:45,202
structures are, are going the analytic 
combinatorics way. 

157
00:12:45,202 --> 00:12:50,041
because it's effective for a very broad 
variety of combinatorial structures, for 

158
00:12:50,041 --> 00:12:53,118
example the unlabelled case that we're 
talking about. 

159
00:12:53,118 --> 00:12:57,809
So we talked about trees there's othere 
types of tree, I'll talk about that in a 

160
00:12:57,809 --> 00:13:00,552
minute, it works for strings or even 
just. 

161
00:13:00,552 --> 00:13:06,042
For properties of numbers for like, for 
compositions, those are sets of numbers 

162
00:13:06,042 --> 00:13:11,727
that sum to N, or partitions where you 
don't take the order into account or for 

163
00:13:11,727 --> 00:13:16,907
languages, for regular languages or 
context free languages are just examples 

164
00:13:16,907 --> 00:13:22,322
of combinatorial structures that we can 
specify and therefore we can analyze with 

165
00:13:22,322 --> 00:13:26,822
analytic combinatorics. 
labels objects are things like 

166
00:13:26,822 --> 00:13:34,062
permutations or balls and urns, or cyclic 
permutations or functions we call words, 

167
00:13:34,062 --> 00:13:41,908
function from 1 finite domain to another. 
label trees those are acyclic mappings or 

168
00:13:41,908 --> 00:13:48,077
general mappings, and many many others. 
these are just the basic ones. 

169
00:13:48,077 --> 00:13:52,282
and not only that, [INAUDIBLE] is fully 
extendible. 

170
00:13:52,282 --> 00:13:57,991
so, new constructions are easy to derive. 
Just use the tools the way you would for 

171
00:13:57,991 --> 00:14:02,304
any formal language. 
And, not only that, if you don't find the 

172
00:14:02,304 --> 00:14:06,292
construction that you need, you can 
develop, a new one. 

173
00:14:06,292 --> 00:14:13,185
and a corresponding transfer theorem, and 
that's happening regularly for all sorts 

174
00:14:13,185 --> 00:14:18,062
of applications. 
so, just to look at some elementary 

175
00:14:18,062 --> 00:14:23,292
examples briefly you can see how over and 
over again we can just go from a 

176
00:14:23,292 --> 00:14:27,687
construction to a generating function 
equation to get the coefficients out. 

177
00:14:27,687 --> 00:14:32,573
Some times the transfer theorems are very 
simple they're just [UNKNOWN] theories 

178
00:14:32,573 --> 00:14:36,975
expansions. 
So, an integer is just a sequence of 

179
00:14:36,975 --> 00:14:40,837
unmarked objects, there, a positive 
integer say. 

180
00:14:40,837 --> 00:14:46,680
so that's z cross sequence of z. 
So that immediately translates to z over 

181
00:14:46,680 --> 00:14:52,782
1-z and number of integers. 
Of size, n is just a 1, for n bigger than 

182
00:14:52,782 --> 00:14:55,607
0. 
And then we can, use, build on that 

183
00:14:55,607 --> 00:15:00,607
construction to talk about partitions and 
compositions and other things. 

184
00:15:00,607 --> 00:15:05,557
Are string, that's our say genomic 
string, it's a four character string, 

185
00:15:05,557 --> 00:15:11,471
it's a sequence of Four different atoms 
so or in this case, say, M different 

186
00:15:11,471 --> 00:15:15,359
atoms. 
but that immediately gives strings from 

187
00:15:15,359 --> 00:15:19,684
the alphabet of size M. 
The generating function, is 1 / 1 - MZ. 

188
00:15:19,684 --> 00:15:25,377
and there's M ^ N of them. 
again very fundamental construction. 

189
00:15:25,377 --> 00:15:33,267
binary trees is the one that we just did, 
that needs an analytic transfer thereom. 

190
00:15:33,267 --> 00:15:36,450
Now, below the line is the labeled 
universe. 

191
00:15:36,450 --> 00:15:39,235
A permutation is a sequence of labeled 
objects. 

192
00:15:39,235 --> 00:15:44,140
the multiply appli operation involves 
relabeling, and I won't get into that 

193
00:15:44,140 --> 00:15:47,256
now, just show what the constructions 
look like. 

194
00:15:47,256 --> 00:15:52,061
And it's exponential generating function, 
so we need to multiply the coefficients 

195
00:15:52,061 --> 00:15:56,319
by n!. 
Huh, Cycles or labeled cycles, it's log 

196
00:15:56,319 --> 00:16:03,404
of 1 over 1-Z and immediately again, 
immediately gives yourself a generating 

197
00:16:03,404 --> 00:16:07,502
function. 
Huh,words is a, if you specify the 

198
00:16:07,502 --> 00:16:14,425
indecise that have each value, it's a 
sequence of sets, and huh, and so the, 

199
00:16:14,425 --> 00:16:21,426
huh, immediately the transfer theorem 
gets you to the Mz and and it's n to the 

200
00:16:21,426 --> 00:16:25,999
m, it's just looking at the same 
commonitorial object in two different 

201
00:16:25,999 --> 00:16:28,816
ways. 
And there's all sort's of benefits of 

202
00:16:28,816 --> 00:16:32,381
doing that. 
Because one of the real sweet spots of 

203
00:16:32,381 --> 00:16:38,092
analytic, upper analytic combinatorics 
and one, one of the reason's is it's so s 

204
00:16:38,092 --> 00:16:44,179
Is, now you take those fundamental 
constructions and transfers that are easy 

205
00:16:44,179 --> 00:16:48,250
to understand. 
And you, once you do it, then you can 

206
00:16:48,250 --> 00:16:52,364
have variations and get the analysis 
immediately. 

207
00:16:52,364 --> 00:16:57,166
So we talked about binary trees, but you 
could do ternary trees. 

208
00:16:57,166 --> 00:17:04,177
Or ordered trees where the, every node 
can have any number of children at all. 

209
00:17:04,177 --> 00:17:10,207
Or you can specify that the number of 
children has to be less than, a given 

210
00:17:10,207 --> 00:17:16,852
value, say 0, 1 or 2 say or you can have 
actually arbitrary restrictions, of any 

211
00:17:16,852 --> 00:17:19,324
kind. 
Or it's gotta be more than 2. 

212
00:17:19,324 --> 00:17:24,756
And there's important applications of 
every 1 of these they're all easily 

213
00:17:24,756 --> 00:17:30,558
handled with symbolic transfer theorems. 
now if sometimes we can get to generating 

214
00:17:30,558 --> 00:17:34,772
function equations that seem difficult to 
deal with. 

215
00:17:34,772 --> 00:17:40,640
a five way tree's going to have a, a 
fifth order polynomial and so forth that 

216
00:17:40,640 --> 00:17:46,533
we might have to work with. 
and that's it might seem challenging, but 

217
00:17:46,533 --> 00:17:51,957
actually, another hallmark of the 
analytic combinatorics , is that, a lot 

218
00:17:51,957 --> 00:17:58,231
of times a single transfer therm can 
Cover eh, a broad, broad variety of 

219
00:17:58,231 --> 00:18:01,376
cases. 
And those are called universal laws that 

220
00:18:01,376 --> 00:18:05,253
are extremely general. 
Now, that's one of the hallmarks of 

221
00:18:05,253 --> 00:18:10,054
analytic combinatorics. 
for example, context-free constructions. 

222
00:18:10,054 --> 00:18:15,053
So, this is when, we can have a whole 
system of combinatorial construction. 

223
00:18:15,053 --> 00:18:19,872
Where the operators is one of the simple 
ones that I've talked about. 

224
00:18:19,872 --> 00:18:25,381
those with the symbolic transfer go 
immediately into a system of generating 

225
00:18:25,381 --> 00:18:28,994
function equations. 
You're going to write those out 

226
00:18:28,994 --> 00:18:32,352
symbolically, they can be pretty 
complicated. 

227
00:18:32,352 --> 00:18:38,304
But, with Grobner basis elimination, for 
whatever it is, it can be reduced down to 

228
00:18:38,304 --> 00:18:43,689
a single generating function equation. 
Now there's certain technical conditions 

229
00:18:43,689 --> 00:18:47,402
to make all this work; I don't want to 
oversimplify it. 

230
00:18:47,402 --> 00:18:53,399
But in, in the end what happens is then 
that single generating function equation 

231
00:18:53,399 --> 00:18:58,260
there's the theorem called the [UNKNOWN] 
theorem that takes that down to an 

232
00:18:58,260 --> 00:19:02,063
explicit solution. 
so for any system of combinatorial 

233
00:19:02,063 --> 00:19:07,024
construction it's always going to have a 
solution of this time with C, B and A 

234
00:19:07,024 --> 00:19:11,888
constants that we can compute. 
Or we can get more [UNKNOWN] accuracy if 

235
00:19:11,888 --> 00:19:15,465
we want. 
So, the analytic transfer theorem from 

236
00:19:15,465 --> 00:19:20,679
singular ring analysis that we just did, 
gives this simple asymptotic form. 

237
00:19:20,679 --> 00:19:26,094
You have a context free construction. 
It's going to be, a over 2 square root of 

238
00:19:26,094 --> 00:19:30,015
pi, a^3 b to the n. 
Where a and be are constants that we can 

239
00:19:30,015 --> 00:19:33,988
compute. 
it's amazingly, general universal law. 

240
00:19:33,988 --> 00:19:38,502
And there's, several universal laws, that 
we know. 

241
00:19:38,502 --> 00:19:44,492
Before analytic combinatorics, you would 
find papers, long papers that used the 

242
00:19:44,492 --> 00:19:49,108
old methods to come up with the results, 
and it was becoming pretty clear to 

243
00:19:49,108 --> 00:19:54,114
experts that there had to be something 
behind square root of pi N ^ 3 appearing 

244
00:19:54,114 --> 00:19:59,485
in the denominator all the time. 
but, we can now know that, why that 

245
00:19:59,485 --> 00:20:02,238
happens because we have the universal 
laws. 

246
00:20:02,238 --> 00:20:07,148
And, again, there's several others, and 
one of the goals of modern research in 

247
00:20:07,148 --> 00:20:12,332
analytic combinatorics is, discover, more 
and more, universal laws. 

248
00:20:12,332 --> 00:20:20,739
so that leads me just to briefly describe 
analytic combinatorics at the next level 

249
00:20:20,739 --> 00:20:25,088
beyond what I've been able to talk about 
right now. 

250
00:20:25,088 --> 00:20:32,741
one thing is that actually often what we 
want is multi-vari Generating functions 

251
00:20:32,741 --> 00:20:39,247
have to handle combinatorial parameters, 
multivariate analytic combinatorics, 

252
00:20:39,247 --> 00:20:44,588
sometimes will give us limit laws about 
the values of, of parameters. 

253
00:20:44,588 --> 00:20:50,222
A lot of times the, the behavior of the 
functions and the complex plane, it's 

254
00:20:50,222 --> 00:20:55,703
very complicated, and we get oscillation 
like that formula that we had, involving 

255
00:20:55,703 --> 00:21:01,013
the data function, is an example of that, 
so the answer is not simple, we have to 

256
00:21:01,013 --> 00:21:04,982
deal with that. 
sometimes there's a method known as 

257
00:21:04,982 --> 00:21:10,932
saddle-point asymptotics that we have to 
use for for generating functions that 

258
00:21:10,932 --> 00:21:16,489
don't have singularities. 
You can do more than just figure out a 

259
00:21:16,489 --> 00:21:21,203
counting sequence from knowing an 
equation that the generating function 

260
00:21:21,203 --> 00:21:24,671
must satisfy. 
One of the things you can do is generate 

261
00:21:24,671 --> 00:21:28,690
random structures. 
And, one of the important applications of 

262
00:21:28,690 --> 00:21:33,235
analytic combinatorics is use 
combinatorial constructions as a basis 

263
00:21:33,235 --> 00:21:38,312
for generating big random structures. 
Which you can compare against real data 

264
00:21:38,312 --> 00:21:43,837
to decide if you have a decent model. 
as I mentioned, and I didn't discuss in 

265
00:21:43,837 --> 00:21:50,347
detail these analytic transfer theorems 
sometimes have technical conditions that 

266
00:21:50,347 --> 00:21:57,192
need to be checked and sometimes that's 
really the burden of completely solving 

267
00:21:57,192 --> 00:22:00,228
the problem. 
And so we want to remove as many such 

268
00:22:00,228 --> 00:22:04,698
conditions as possible. 
and the other thing is, when another 

269
00:22:04,698 --> 00:22:09,838
thing is, when, when we get into analysis 
of algorithms, we're often talking about, 

270
00:22:09,838 --> 00:22:14,955
with programs, transforming data. 
from one structure, one combinatorial 

271
00:22:14,955 --> 00:22:21,636
structure to another, which is a complex 
process that's, difficult to capture, 

272
00:22:21,636 --> 00:22:28,794
maybe even with, analytic combinatorics. 
and then also, we Easily can construct, 

273
00:22:28,794 --> 00:22:35,040
specify constructions that lead to, 
relatively complicated, implicit 

274
00:22:35,040 --> 00:22:42,203
functional equations, that are maybe not 
so easy to handle with, analytic transfer 

275
00:22:42,203 --> 00:22:46,682
theorem. 
but still there's a very broad variety of 

276
00:22:46,682 --> 00:22:52,772
problems that that can be handled simply 
with combinatorial constructions 

277
00:22:52,772 --> 00:22:58,737
transferring immediately to generating 
function equations and then translating 

278
00:22:58,737 --> 00:23:03,137
to coefficient asymptotics one step after 
another. 

279
00:23:03,137 --> 00:23:09,162
For example that's partitions. 
how many ways are there to Write an 

280
00:23:09,162 --> 00:23:14,537
integer as sum of other integers, of 
smaller integers. 

281
00:23:14,537 --> 00:23:22,172
so [COUGH], a combinatorial construction 
for that is multiset and the transfer 

282
00:23:22,172 --> 00:23:28,259
theorem immediately gives the The 
generating function, 1 / 1 - Z, and so 

283
00:23:28,259 --> 00:23:34,476
forth and then there's a, analytic 
transfer theorem that immediately gives 

284
00:23:34,476 --> 00:23:40,288
the coefficient the asymptotics. 
so, just another example, series parallel 

285
00:23:40,288 --> 00:23:45,001
networks, where this is a model for for 
Boolean expressions and electric 

286
00:23:45,001 --> 00:23:49,163
circuits, and many other things. 
and so, you want to know how many of 

287
00:23:49,163 --> 00:23:53,787
those are, how many bits would you need 
to represent one or study some parameter 

288
00:23:53,787 --> 00:23:56,455
of it. 
You can use a combinatorial, a simple, 

289
00:23:56,455 --> 00:24:00,819
combinatorial construction. 
Get a simple generating function 

290
00:24:00,819 --> 00:24:06,209
equation, that is amenable to the 
standard transfer therm where the 

291
00:24:06,209 --> 00:24:11,515
exponent is 1/3-^8. 
relatively straight forward to study such 

292
00:24:11,515 --> 00:24:17,577
problems with analytic combinatorics. 
so surjections, that's the number of 

293
00:24:17,577 --> 00:24:23,913
mappings onto initial sequences of the 
integers, and of how that's got lots of 

294
00:24:23,913 --> 00:24:30,184
applications and again it's a sequence of 
a set immediately gives the generating 

295
00:24:30,184 --> 00:24:36,106
function and then be, it's 1 over 2 - 
Z(z) so the similarities are 2 over log2 

296
00:24:36,106 --> 00:24:37,725
N. 
at, at log 2. 

297
00:24:37,725 --> 00:24:42,443
And, so that gives the asymptotics, 
immediately. 

298
00:24:42,443 --> 00:24:48,171
components in, in mappings. 
so a mapping is a function from the 

299
00:24:48,171 --> 00:24:52,872
integers 1, through n to itself. 
and, that. 

300
00:24:52,872 --> 00:24:58,931
[COUGH], gives the, the [UNKNOWN] with 
the two constructions. 

301
00:24:58,931 --> 00:25:05,172
It's a cycle of trees, really, and a tree 
is, a node and set of trees. 

302
00:25:05,172 --> 00:25:11,335
so that's what those constructions say, 
and they immediately translate into those 

303
00:25:11,335 --> 00:25:16,002
generating function equations, and then 
we have transfer theorems that 

304
00:25:16,002 --> 00:25:19,636
immediately give the coefficient 
asymptotics. 

305
00:25:19,636 --> 00:25:25,047
So, it's a very, very long list of 
standard combinatorial objects, and 

306
00:25:25,047 --> 00:25:30,672
combinatorial parameters that are 
classical objects, that are amenable to 

307
00:25:30,672 --> 00:25:36,022
study with analytic combinatorics. 
And then, all kinds of new objects that 

308
00:25:36,022 --> 00:25:43,230
were Too complicated to deal with using 
classical techniques, that people have 

309
00:25:43,230 --> 00:25:48,464
studied and learned properties of, with 
analytic combinatorics. 

310
00:25:48,464 --> 00:25:51,765
If you can specify it, you can analyze 
it. 

311
00:25:51,765 --> 00:25:58,862
so that's what's in our 2009 book, this 
is an, an overview of what's inside and 

312
00:25:58,862 --> 00:26:04,446
how it's related and, and what Comes out 
so the first thing is the symbolic 

313
00:26:04,446 --> 00:26:10,267
methods, the symbolic transfer theorems 
for labeled objects, unlabeled objects, 

314
00:26:10,267 --> 00:26:15,963
and parameters corresponding to ordinary 
exponential, and multivariate generating 

315
00:26:15,963 --> 00:26:19,301
functions. 
From those symbolic methods, you can 

316
00:26:19,301 --> 00:26:25,029
either go into complex asymptotics to go 
ahead and get out the asymptotic counting 

317
00:26:25,029 --> 00:26:30,239
results as I've discussed but you can 
also get out moments of parameters as 

318
00:26:30,239 --> 00:26:33,870
well. 
and you can get properties of random 

319
00:26:33,870 --> 00:26:40,967
structures and limit laws as well. 
So that's again, in a short lecture the 

320
00:26:40,967 --> 00:26:47,692
best I could do to describe, really what 
is analytic combinatorics. 

321
00:26:47,692 --> 00:26:52,667
and so, 2009 we think this one is, is 
solved. 

322
00:26:52,667 --> 00:26:59,507
it's got All kinds of applications from 
studying patterns in random strings with 

323
00:26:59,507 --> 00:27:05,617
finite fields, standard algorithms like: 
hashing, data compression, geometric 

324
00:27:05,617 --> 00:27:11,925
search, chemistry, it has combinatorics, 
and one, and one of the original 

325
00:27:11,925 --> 00:27:18,587
history's of our field was Polya, George 
Polya studying application in chemistry. 

326
00:27:18,587 --> 00:27:22,553
there's a connection to analytic number 
theory. 

327
00:27:22,553 --> 00:27:27,895
people are studying planar maps and 
graphs and probabilistic stream 

328
00:27:27,895 --> 00:27:32,657
algorithms. 
we have a solution to a standard, theorem 

329
00:27:32,657 --> 00:27:37,275
in computer science that is based on 
analytic combinatorics. 

330
00:27:37,275 --> 00:27:43,530
Bioinformatics is a very rich and fertile 
area of application, and statistical 

331
00:27:43,530 --> 00:27:49,432
physics, and Automatic testing of 
programs and, many, many others. 

332
00:27:49,432 --> 00:27:52,597
If you can specify it, you can analyze 
it. 

333
00:27:52,597 --> 00:27:57,282
and analytic combinatorics is here to 
stay, here to stay. 

334
00:27:57,282 --> 00:28:02,712
So I mentioned that it was 30 years, in 
the making to get to the book. 

335
00:28:02,712 --> 00:28:08,652
And I just want to finish by, pointing 
out that, we're still counting. 

336
00:28:08,652 --> 00:28:14,760
Though, there's is a second edition now, 
the original analysis for Algorithm book 

337
00:28:14,760 --> 00:28:19,782
that I did, that includes and 
introduction to analytic combinatorics, a 

338
00:28:19,782 --> 00:28:25,903
and I know Felippe always wanted that. 
And more than that, there's extensive web 

339
00:28:25,903 --> 00:28:31,649
content in the process of development. 
and also online course. 

340
00:28:31,649 --> 00:28:39,976
So it's a very active and vibrant field 
if you want to learn more about analytic 

341
00:28:39,976 --> 00:28:43,942
combinatorics there are many ways to do 
so. 

342
00:28:43,942 --> 00:28:49,227
I've given a lecture like this, many 
times since Philippe's death. 

343
00:28:49,227 --> 00:28:54,562
and I, at first, ended with saying, it 
was a pleasure to work with Philippe. 

344
00:28:54,562 --> 00:28:59,847
But now I think it's better to say that 
it's a pleasure to be working with him 

345
00:28:59,847 --> 00:29:03,832
because I feel that I'm still working 
with Philippe. 

346
00:29:03,832 --> 00:29:08,684
I, and I hope that many more of you have 
the opportunity to do so through the 

347
00:29:08,684 --> 00:29:10,794
materials that I've discussed.