Analytic combinatorics
by Philippe Flajolet · first published 2009
57% recommend43% neutral
Why HN recommends it
Covers generating functions and asymptotic analysis for counting problems, with a practical trick for classroom-style puzzles; suited to CS and discrete math students and those wanting deep combinatorics theory.
Summarised by Claude from recommending comments
Analytic combinatorics aims to enable precise quantitative predictions of the properties of large combinatorial structures. The theory has emerged over recent decades as essential both for the analysis of algorithms and for the study of scientific models in many disciplines, including probability theory, statistical physics, computational biology, and information theory. With a careful combination of symbolic enumeration methods and complex analysis, drawing heavily on generating functions, results of sweeping generality emerge that can be applied in particular to fundamental structures such a
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
Mentions per year
What Hacker News says
Related books
Generatingfunctionology
Herbert S. Wilf
Recommended by 9 · mentioned by 139 recommend · 13 mention9 recommend · 139 recommend
2008–2026Linear Algebra Done Right
Sheldon Jay Axler
Recommended by 130 · mentioned by 179130 recommend · 179 mention130 recommend · 179130 recommend
2007–2026Concrete mathematics
Ronald L. Graham, Donald Knuth, Oren Patashnik
Recommended by 140 · mentioned by 215140 recommend · 215 mention140 recommend · 215140 recommend
2007–2026The art of computer programming
Donald Knuth
Recommended by 336 · mentioned by 1,125336 recommend · 1,125 mention336 recommend · 1,125336 recommend
Here's a fun trick I learned from Flajolet and Sedgewick's Analytic Combinatorics (available online, page 52). I imagine it will seem incredible when tried with an actual classroom: > Révész in [Strong theorems on coin tossing] tells the following amusing story attributed to T. Varga:…
on “How random can you be?” ↗…math students among you. Feel free to add some of yours, I'm hardly the veteran educator here. Knuth, Graham, Patashnik's Concrete Mathematics, after a few chapters, goes well with Flajolet, Sedgewick's Analytic Combinatorics. You should mix that up with some Discrete Mathematics introductory book, especially one dealing with counting objects, so you can apply the techniques almost immediately on simpler examples. Papadimitrou,…
on “Math ∩ Programming” ↗Another great resource on generating functions is Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick: http://algo.inria.fr/flajolet/Publications/book.pdf
on “Fibonacci series and Dynamic programming” ↗I warmly recommend Analytic Combinatorics by Flajolet & Sedgewick, freely downloadable at http://algo.inria.fr/flajolet/Publications/book.pdf I like the books you mentioned, but this one I love.
on “I'm writing a book about algorithms and Lisp” ↗Flajolet and Sedgewick have a nice book on Analytic Combinatorics that covers this
on “A Non-Constructive Proof of the Four Colour Theorem” ↗Generating functions are also a great tool in combinatorics (see for example the book Analytic Combinatorics by Flajolet and Sedgewick).
on “Probability-generating functions” ↗…handled well by the Master theorem ( https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_al... ). For those deeply interested in the deep math of combinatorics I recommend Flajolet, Sedgewick, *Analytic Combinatorics, Cambridge 2009.
on “What Every Programmer Should Know About Enumerative Combinatorics” ↗…probability-generating functions are and how to intuit them. There were two pieces of the puzzle missing for me, and we’ll go through both in this article." Great article. For more, I really recommend Analytic Combinatorics: https://ac.cs.princeton.edu/home/
on “Probability-generating functions” ↗…output, and repeat until it converges. The problem is that you could end up in a cycle, instead of at a fixed point. The speed with which it can be found: I'm going to wave my hands and claim this is in "Analytic Combinatorics" by Flajolet and Sedgewick. Seriously, though, under the assumptions we've been throwing around here this is a "random mapping" and these are reasonably well-studied objects.
on “Using http:// and .com is madness” ↗…for putting more mathematics into Computer Science. I think this is an important long-term trend. Last year I read Bergeron et al's Combinatorial Species and then dipped into Flajolet and Sedgewick's Analytic Combinatorics. The first of these is concerned with mathematical structures that are tantalizingly close (or identical) to data structure that we often use. These can be represented as algebraic expressions and converted…
on “Putting the Science back in Computer Science” ↗The "Analytic Combinatorics"[1] book by Flajolet and Sedgewick is also relevant here. [1] http://algo.inria.fr/flajolet/Publications/book.pdf
on “The Algebra of Algebraic data types” ↗…of binary trees with i nodes of height <= n. If we did, we could approximate the Mandelbrot and it would unlock new frontiers of understanding chaos theory. Philippe Flajolet, a now-deceased titan of analytic combinatorics [2] wrote some papers on the problem, but never got more than rough asymptotic bounds. https://www.sciencedirect.com/science/article/pii/0022000082... Further work was done here: https://www.labri.fr/Perso/~bousquet/Exposes/trees.pdf…
on “Flipping until you are lost” ↗There's an interesting extension to Analytic Combinatorics by Flajolet/Sedgewick called "Analytic Combinatorics in Several Variables" by Pemantle and Wilson: https://www2.math.upenn.edu/~pemantle/papers/ACSV.pdf and https://acsvproject.com/ It extends the original…
on “Analytic Combinatorics – A Worked Example” ↗…Algorithms; there's a course website at https://aofa.cs.princeton.edu/home/ and videos on Coursera (https://www.coursera.org/learn/analysis-of-algorithms) — it is advanced mathematics but less advanced than the Analytic Combinatorics book.
on “Analytic Combinatorics – A Worked Example” ↗…(obviously I've read only a tiny bit of it) has problem ratings and sometimes very terse solutions / outlines of solutions. • Uspensky and Heaslet's Elementary Number Theory (which I read before Burton) and Analytic Combinatorics have no solutions at all. I don't think solutions to exercises have made a substantial difference in my engagement with these books, but who knows.
on “Books I Recommend” ↗