In recent years, a lot of people have 
asked me just what the phrase analytic 
combinatorics actually means. 
In this lecture, I'm going to describe 
what the field is and tell the story of 
how it came into being. 
I think this context is important for 
anyone who's interested in learning 
anything about the field. 
this lecture is dedicated to the memory 
of my friend and colleague, Philippe 
Flajolet, who really was the driving 
force behind the development of the field 
and who died suddenly in 2011. 
I'll start off with a brief history to 
try to give some context for how we got 
there. 
I first met Philippe in 1977. 
my first research paper that I wrote 
after getting my Ph.D. was on an 
algorithm called Odd-Even Merging and I, 
I went to a, in those days you would get 
your paper typed by a secretary and go to 
a conference and present it. 
and I was very proud to have developed 
this formula that involves the gamma 
function and the zeta function, and gives 
a precise description of the performance 
of this particular algorithm. 
and just a few months later we had a 
conference in Providence, Rhode Island, 
where I was at the time. 
and in, in those days you go to the 
conference and the first thing you do in 
the proceedings is go and and look at the 
table of contents and recedings and see 
what's there, and there was another type 
paper. 
And I was amazed to see a formula very 
much like mine involving the zeta 
function and the gamma function even 
though it was studying a completly 
different problem. 
and just as I was realizing that, 
Philippe came up to me and said, I 
believe that we have a formula in common. 
and both of us were very surprised to see 
the similiarities among these formulas 
and it might be said that we spent the 
rest of our careers trying to understand 
why. 
now it's worth it to think about what the 
world was like at the time that we 
started our research careers. 
and we were both, at that time, in the, 
just the early part of our research 
careers. 
and the world was changing in very 
important ways all around us without 
going into too much detail. It really was 
the case that when we started school 
people wore coats and ties, wear coats 
and ties to dinner and so forth. 
But by the time we got out P.h.Ds 
there was Woodstock and hippies and and 
so forth and, but, with respect to 
technology, there were huge changes. 
when we started school, computers were 
big. 
expensive rare there were physical 
devices for every switch or for every 
bit. 
but not that much longer when we started 
research in teaching we had integrated 
circuits and computers were becoming 
ubiquitous and fast and cheap. 
another big thing was the access to 
computers. 
most of the time that we were in college 
and in graduate school you would get to 
develop a program you had to put each 
line of the program on a punched card and 
you had to give a box of punched cards to 
a computer operator and you would get to 
run your program once a day. 
not that much longer, we had later when 
we started research in teaching we had 
timeshared terminals and we're always 
connected and have been connected ever 
since. 
And as I mentioned, when we started 
school my thesis was typed by a 
secretary. 
so you present the result and 6 months 
later, you sort of see what it looked 
like and submitted it. It might be it 
might be a year between the time that you 
get the results and somebody sees it but 
not that much longer, we had word 
processing and and mathematical type 
setting and we can have a much quicker, 
and much broader communication of our, of 
our research results. 
And another important thing is that when 
we were in school and graduate school the 
curriculum was about math everybody 
learned lots of math and I learned PDEs, 
and abstract alegebra, and probability, 
and topology. 
that's what that's what people with an 
interest in working in technical fields 
did. 
but by the time we started researching 
teaching, there was computer science and 
people had to learn about compilers, and 
algorithms, and data structures, and 
graphics, and operating systems and 
programming languages, numerical 
analysis, and all kinds of fields related 
to computer science. 
So these are huge differences in a 
relatively short amount of time and in 
thinking about it when preparing this 
talk, I really came to understand and 
believe that this was a really profound 
change in the way the world worked. 
maybe even more profound than the [COUGH] 
evolution of PCs, personal computing or, 
or even the Internet. 
the world was a vastly different place 
when we started to get to work. 
so that's the context where, where this 
story starts. 
now, analysis of algorithms. 
So that's the field of study that both 
Philippe and I were engaged in and it's 
actually natural in each, in questions 
and it actually started with Babbage. 
so this is a quote from from Babbage 
whose widely attributed to have one of, 
maybe the first comp, designed the first 
computational engine, it was a mechanical 
device that could do arithmetic 
computations. 
and what he said even before building the 
thing as soon as an analytic engine 
exists, it will necessarily guide the 
future course of the science, 
because you'd be able to do computations. 
but he said whenever any result is 
sought, the question will arise by what 
course of calculation can these results 
be arrived at by the machine in the 
shortest time? That's in 1864 and you can 
see why it was important to Babbage. 
This thing actually had a crank and the 
only way that it could compute things was 
by somebody turning the crank. 
Obviously you want to minimize the number 
of times that you need to turn the crank. 
The computers were expensive and slow and 
and used energy and so forth, and so 
minimizing the cost of computation was 
always very important. 
even Turing who many who, who is, is 
[COUGH] the founder of theoretical 
computer science could see the importance 
of these kinds of practical questions. 
we want to have a measure of the amount 
of work involved in a computing process, 
even though, it might be a crude one. 
We count up the number of times that 
elementary operations are applied in the 
whole process and, and, in order to 
figure out how much work it's going to 
take before to help in designing 
efficient computation. 
But the field of analysis of algorithms 
was really initiated by Knuth in the 
1960s. 
and what Knuth told the world, and there 
was some debate about it at the time, was 
that classical mathematics, as we got the 
necessary tools that we need for 
understanding the performance of 
algorithms. 
there's things like recurrence relations, 
and generating functions, and asymptotic 
analysis that has the benefit of giving a 
scientific foundation for the analysis of 
algorithms and Knuth wrote a series of 
four books so far. 
First one came out in, in the late 60s 
and two more came out in the early 70s. 
We really set up this scientific 
foundation. 
We really can use classic mathematic to 
understand the performance of algorithms 
in, with those mathematical models we 
could go ahead and accurately predict 
performance and compare the efficiency of 
algorithms. 
in that's what we found exciting we could 
use classical mathematics to understand. 
Now, the cost of a computation and then 
test up those results in [COUGH] 
formulate hypothesis about how long we 
take to do something, and then validate 
those hypothesis by actually 
implementing, and running a program, and 
checking them against the math. 
There are many many practical 
applications where people needed the have 
these kinds of accurate math, math, math 
models and, and predictions. 
and in Knuth's books we're very densely 
filled with this information that helped 
us advance this science. 
So that's a brief history of where we got 
started with analysis of algorthm.