Analytic combinatorics

What Hacker News says

1. jmountMay 2025
   As a fan of combinatorics, I love people looking into the topic. Though most of what a programmer would find useful are approximations or trends which are 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.
   thread
2. JPC21Oct 2024
   Generating functions are also a great tool in combinatorics (see for example the book Analytic Combinatorics by Flajolet and Sedgewick).
   thread
3. pedrothOct 2024
   "I have long struggled with understanding what 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/

   thread
4. selimthegrimDec 2022
   Flajolet and Sedgewick have a nice book on Analytic Combinatorics that covers this
   thread
5. milemiJul 2019
   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.
   thread
6. svatMar 2019
   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: “A class of high school children is divided into two sections. In one of the sections, each child is given a coin which he throws two hundred times, recording the resulting head-and-tail sequence on a piece of paper. In the other section, the children do not receive coins, but are told instead that they should try to write down a ‘random’ head-and-tail sequence of length two hundred. Collecting these slips of paper, [a statistician] then tries to subdivide them into their original groups. Most of the time, he succeeds quite well.”

   > The statistician’s secret is [...] in a randomly produced sequence of length 200, there are usually runs of length 6 or more: the probability of the event turns out to be close to 97%. On the other hand most children (and adults) are usually afraid of writing down runs longer than 4 or 5 as this is felt as strongly “non-random”. The statistician simply selects the slips that contain runs of length 6 or more as the true random ones. Voilà!

   ----

   Obviously, the way to beat this site (or the above classroom trick) would be to use "true" random numbers. But if one doesn't have access to coins or computers, it raises the question: what is a good way to generate a long sequence of reasonably random coin flips in one's head? For example, if you've memorized many digits of pi or e or some such "believed to be normal" constant, you could use whether each digit is odd or even (or maybe even something like throw away 8 and 9, and read each remaining digit in octal to get 3 random bits). But that only gets you so far...

   Show morethread