# Analytic Combinatorics

### From charlesreid1

Book by Philipe Flajolet and Robert Sedgewick.

## Contents

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

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:

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

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

# 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

# Flags

AlgorithmsSeries on Algorithms
Algorithms/Sort Three solid O(n log n) search algorithms: Merge Sort Algorithm Analysis/Merge Sort
Algorithms/Search
Algorithms/Combinatorics
Algorithms/Strings
Algorithm complexity Amortization Algorithm Analysis/Matrix Multiplication
Estimation
Project Euler
· Template:AlgorithmsFlag · e |