Welcome to MathOverflow

Question

8

3

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

asked May 25 2011 at 20:28

Austin Mohr

community wiki

Richard Stanley · Answer 1 · 2011-05-25 20:37:25Z UTC

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.

David Speyer · Answer 2 · 2011-05-26 00:49:55Z UTC

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.)

Igor Rivin · Answer 3 · 2011-05-25 20:33:31Z UTC

4

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

answered May 25 2011 at 20:33

Igor Rivin

community wiki

David Speyer · Answer 4 · 2011-05-25 20:51:00Z UTC

4

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

answered May 25 2011 at 20:51

David Speyer

community wiki

David Speyer · Answer 5 · 2011-05-25 20:59:10Z UTC

4

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.

answered May 25 2011 at 20:59

David Speyer

community wiki

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. – Igor Rivin May 25 2011 at 21:04

1

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." – David Speyer May 25 2011 at 21:21

1

Pemantle gave a series of six lectures on this at the 2009 Cornell Probability Summer School : math.upenn.edu/~pemantle/… . There are also lecture notes for a semester-long graduate course at math.upenn.edu/~pemantle/581-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. – Michael Lugo May 25 2011 at 21:34

Asymptotic Methods in Combinatorics

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

5 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.