11
$\begingroup$

What are good texts to acquaint oneself with standard asymptotic techniques, particularly as they relate to probabilistic combinatorics?

$\endgroup$

5 Answers 5

18
$\begingroup$

Philippe Flajolet and Robert Sedgewick's Analytic Combinatorics is the most comprehensive reference, available at http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html. Also useful is Odlyzko's "Asymptotic methods in enumeration" (from The Handbook of Combinatorics) at http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.pdf.

$\endgroup$
9
$\begingroup$

At a lower level than Flajolet and Sedgewick, Chapter 5 of generatingfunctionology by Wilf is a good introduction to complex analytic methods. (Yes, my two answers look very similar. As usual in a big list question, I am posting separate answers so people can vote on them separately.)

$\endgroup$
0
5
$\begingroup$

At a lower level than Flajolet and Sedgewick, Chapter 9 of Concrete Mathematics (Graham, Knuth and Patashnik) is a good introduction to elementary methods.

$\endgroup$
5
$\begingroup$

If you want to know about quantities which (1) have nice generating functions and (2) depend on more than one parameter, the most thorough guide will be found in the papers of Robin Pemantle. to the best of my knowledge, he hasn't written a comprehensive guide to his work; his SIAM report might be the best starting point.

$\endgroup$
3
  • $\begingroup$ Pemantle's work is very impressive, but the problems there are very hard, and if you actually want to know some asymptotics, you should avoid the multivariable case. $\endgroup$
    – Igor Rivin
    May 25, 2011 at 21:04
  • 2
    $\begingroup$ Agreed. Pemantle's work for me is in the category of "if you have to solve this sort of problem, he will tell you how, but try to think about whether you can solve a simpler problem instead." $\endgroup$ May 25, 2011 at 21:21
  • 1
    $\begingroup$ Pemantle gave a series of six lectures on this at the 2009 Cornell Probability Summer School : math.upenn.edu/~pemantle/Cornell-Lectures-2009.html . There are also lecture notes for a semester-long graduate course at math.upenn.edu/~pemantle/581-html/lecture-notes.html (which I took) but these are somewhat incomplete; in particular in those courses we never really got to doing examples. There are plenty of references there for the theory, though. $\endgroup$ May 25, 2011 at 21:34
4
$\begingroup$

Flajolet and Sedgewick, Analytic Combinatorics (available for free, if you like, on the (sadly, late) Flajolet's web page.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.