Analytic Combinatorics - Revision history

Admin: Fix math syntax: add summation bounds to \sum_{n} → \sum_{n \ge 0}, and fix typo "numers" → "numbers" (via update-page on MediaWiki MCP Server)

2026-06-06T00:36:51Z

Fix math syntax: add summation bounds to \sum_{n} → \sum_{n \ge 0}, and fix typo "numers" → "numbers" (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 00:36, 6 June 2026
Line 10:		Line 10:
	"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."		"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:		he states that, regarding the progression of the numbers 1, 2, 5, 14, 42, 132, etc, he observed that the generating function was:

	<math>		<math>
Line 33:		Line 33:

	<math>		<math>
	T(z) = \sum_{n} T_n z^n = \dfrac{1 - \sqrt{1 - 4z}}{2z}		T(z) = \sum_{n \ge 0} T_n z^n = \dfrac{1 - \sqrt{1 - 4z}}{2z}
	</math>		</math>

Admin: /* Related */

2017-07-22T11:33:10Z

← Older revision		Revision as of 11:33, 22 July 2017
Line 38:		Line 38:

	=Related=		=Related=

			Combinatorics notes: [[Combinatorics]]

			Design of algorithms for combinatoric problem spaces: [[Algorithms/Combinatorics]]

	Book notes on <u>Applied Combinatorics</u> by Keller and Trotter: [[Applied Combinatorics]]		Book notes on <u>Applied Combinatorics</u> by Keller and Trotter: [[Applied Combinatorics]]

Admin at 10:17, 22 July 2017

2017-07-22T10:17:59Z

← Older revision		Revision as of 10:17, 22 July 2017
Line 1:		Line 1:
	Book by Philipe Flajolet and Robert Sedgewick.		Book by Philipe Flajolet and Robert Sedgewick.


	=Historical Notes=		=Historical Notes=
Line 36:		Line 37:


			=Related=

			Book notes on <u>Applied Combinatorics</u> by Keller and Trotter: [[Applied Combinatorics]]

			Book notes on Knuth's <u>Art of Computer Programming</u>: [[AOCP]]

	=Flags=		=Flags=

Admin at 10:15, 22 July 2017

2017-07-22T10:15:29Z

← Older revision		Revision as of 10:15, 22 July 2017
Line 34:		Line 34:
	T(z) = \sum_{n} T_n z^n = \dfrac{1 - \sqrt{1 - 4z}}{2z}		T(z) = \sum_{n} T_n z^n = \dfrac{1 - \sqrt{1 - 4z}}{2z}
	</math>		</math>




Line 41:		Line 43:

	{{AlgorithmsFlag}}		{{AlgorithmsFlag}}

	[[Category:Combinatorics]]		[[Category:Combinatorics]]
	[[Category:Generating Functions]]		[[Category:Generating Functions]]

			[[Category:Book Notes]]
			[[Category:Reading]]

Admin at 10:12, 22 July 2017

2017-07-22T10:12:47Z

← Older revision		Revision as of 10:12, 22 July 2017
Line 34:		Line 34:
	T(z) = \sum_{n} T_n z^n = \dfrac{1 - \sqrt{1 - 4z}}{2z}		T(z) = \sum_{n} T_n z^n = \dfrac{1 - \sqrt{1 - 4z}}{2z}
	</math>		</math>




			=Flags=

			{{AlgorithmsFlag}}
			[[Category:Combinatorics]]
			[[Category:Generating Functions]]

Admin: /* Chapter 1 */

2017-07-22T10:12:04Z

Chapter 1

← Older revision		Revision as of 10:12, 22 July 2017
Line 20:		Line 20:

	<math>		<math>
	T_n = \~~sqrt_~~{k=0}^{n-1} T_k T_{n-1-k} \qquad T_0 = 1		T_n = \sum_{k=0}^{n-1} T_k T_{n-1-k} \qquad T_0 = 1
	</math>		</math>

Admin: Created page with "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 qu..."

2017-07-22T10:11:34Z

Created page with "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 qu..."

New page

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:

<math>
1 + 2a + 5a^2 + 14a^3 + 42a^4 + 132a^5 + \dots = \dfrac{1 - 2a - \sqrt{1-4a}}{2a^2}
</math>

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:

<math>
T_n = \sqrt_{k=0}^{n-1} T_k T_{n-1-k} \qquad T_0 = 1
</math>

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

<math>
T_n = \dfrac{1}{n+1} \binom{2n}{n}
</math>

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

<math>
T(z) = \sum_{n} T_n z^n = \dfrac{1 - \sqrt{1 - 4z}}{2z}
</math>