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 numbers 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:

$ 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:

$ T_n = \dfrac{1}{n+1} \binom{2n}{n} $

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

$ T(z) = \sum_{n \ge 0} 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