Analytic Combinatorics – A Worked Example

This is only tangentially related, but one thing that I am still kind of hopeful about is analytic combinatorics will free us from the <i>tyranny</i> of asymptotic analysis.<p>I suppose this is kind of a hot take, and in some ways less relevant than it was (say) 10 years ago, but I believe the theoretical CS community has spent a lot of time analyzing the performance of various algorithms over the years and kind of pointedly not inventing algorithms which accomplish some result at all, even if it is only known to be computable in a pathologically inefficient way. This means a lot of breakthroughs that could have been TCS breakthroughs have been invented, usually worse, by other communities.<p>I am not the only one who thinks so, here[1] is an obscure talk where Michael Mitzenmacher (a well-known CS theory prof at Harvard) makes more or less this specific complaint.<p>One of the nice things about Flajolet&#x2F;Sedgewick[2] (mentioned in this post) is that it gives a nice set of combinators for (at least it seems to me, in theory) precisely enumerating how many &quot;steps&quot; an algorithm would take given some input. I optimistically imagine a world where we replace the relatively non-specific asymptotic bounds of an algorithm with a very specific quantification of the work an algorithm will take. And that this in turn would free TCS to focus on things that are more germane to the field as a whole.<p>With that all said I&#x27;m open to the argument that TCS has fundamentally changed and this is no longer such a big issue. But perusing the various TCS conferences I sense it isn&#x27;t.<p>[1]: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=p3anjSAnKBo" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=p3anjSAnKBo</a><p>[2]: <a href="https:&#x2F;&#x2F;algo.inria.fr&#x2F;flajolet&#x2F;Publications&#x2F;book.pdf" rel="nofollow">https:&#x2F;&#x2F;algo.inria.fr&#x2F;flajolet&#x2F;Publications&#x2F;book.pdf</a>

Very cool!<p>What&#x27;s meant by &quot;it’s already too much to ask for a closed form for fibonacci numbers&quot;? Binet&#x27;s formula is usually called a closed form in my experience. Is &quot;closed form&quot; here supposed to mean &quot;closed form we can evaluate without needing arbitrary-precision arithmetic&quot;?

This article gets things wrong and overcomplicates other things.<p>he confuses the characteristic equation for the generating function. This : T(z) = z + zT + zT^2 + zT^3 is the characteristic equation.<p>There is no simple generating function ,as it&#x27;s not possible to easily invert a cubic closed in form.<p>Successive derivatives of the generating function are taken to find the coefficients of the infinite series that encodes the sought values. It&#x27;s hard enough explaining this with a quadratic; a cubic so much more involved.<p>This so far beyond the scope of a blog post. You need to spend at least a few weeks working on this or take some college courses.

There&#x27;s an interesting extension to Analytic Combinatorics by Flajolet&#x2F;Sedgewick called &quot;Analytic Combinatorics in Several Variables&quot; by Pemantle and Wilson: <a href="https:&#x2F;&#x2F;www2.math.upenn.edu&#x2F;~pemantle&#x2F;papers&#x2F;ACSV.pdf" rel="nofollow">https:&#x2F;&#x2F;www2.math.upenn.edu&#x2F;~pemantle&#x2F;papers&#x2F;ACSV.pdf</a> and <a href="https:&#x2F;&#x2F;acsvproject.com&#x2F;" rel="nofollow">https:&#x2F;&#x2F;acsvproject.com&#x2F;</a><p>It extends the original framework with a lot of useful new primitives, like Hadamard products. Super useful!

What math lets you most easily be convinced you’ve come up with the right answer when you actually haven’t?<p>Seems like combinatorics comes in second only to statistics.

in Haskell you can read off the generating function&#x27;s coefficients directly from the functional equation T(z) = z + zT + zT² + zT²<p>ghci&gt; ts=0:(1+ts+ts^2+ts^3) ghci&gt; take 12 ts [0,1,1,2,5,13,36,104,309,939,2905,9118]<p>Using the Num instance for power series (very cute application of laziness expounded by Karczmarczuk and then McIlroy <a href="https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;abs&#x2F;10.1017&#x2F;s0956796899003299" rel="nofollow">https:&#x2F;&#x2F;dl.acm.org&#x2F;doi&#x2F;abs&#x2F;10.1017&#x2F;s0956796899003299</a>)

I find this interesting but the nomenclature escapes me: How is T(z) = z + zT + zT^2 + ... ? I find the jump from the functional programming description of the tree to this recurrence relation not intuitive

This article is technically way beyond me, but can anybody explain to me what on earth a &quot;worked example&quot; is? That expression is completely incoherent.

The key is to always square the generating function—it doesn’t matter why, it just feels more correct. Learned that from a proof in an old cereal box puzzle.