Analytic Combinatorics

Book by Philipe Flajolet and Robert Sedgewick.

Historical Notes

Chapter 1

On September 4, 1751, Euler wrote to his friend Goldbach:

"I have recently encountered a question, which appears to me rather noteworthy. It concerns the number of ways in which a given [convex] polygon can be decomposed into triangles by diagonal lines."

he states that, regarding the progression of the numers 1, 2, 5, 14, 42, 132, etc, he observed that the generating function was:

$1+2a+5a^{2}+14a^{3}+42a^{4}+132a^{5}+\dots ={\dfrac {1-2a-{\sqrt {1-4a}}}{2a^{2}}}$

Euler communicated the problem to Segner, who wrote in a paper (1758): "The great Euler has benevolently communicated these numbers to me; the way in which he found them, and the law of their progression having remained hidden to me."

Segner developed a recurrence approach to the Catalan numbers: via root decomposition, he showed the recurrence relation was:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T_n = \sum_{k=0}^{n-1} T_k T_{n-1-k} \qquad T_0 = 1 }

In the 1830s Liouville circulated the problem; Lame answered with a proof based on recurrences of the form:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T_n = \dfrac{1}{n+1} \binom{2n}{n} }

Catalan finally proved the validity of Euler's generating function:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle T(z) = \sum_{n} T_n z^n = \dfrac{1 - \sqrt{1 - 4z}}{2z} }

Related

Combinatorics notes: Combinatorics

Design of algorithms for combinatoric problem spaces: Algorithms/Combinatorics

Book notes on Applied Combinatorics by Keller and Trotter: Applied Combinatorics

Book notes on Knuth's Art of Computer Programming: AOCP