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:

$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}T_{n}z^{n}={\dfrac {1-{\sqrt {1-4z}}}{2z}}$

Flags

Analytic Combinatorics

From charlesreid1

Contents

Historical Notes

Chapter 1

Related

Flags