Math 2.0

Combinatorics Theorem

Catalan recurrence

Builds on Catalan numbers

Statement

Let nn be a natural number, and let CmC_m be the Catalan numbers. Then Cn+1=∑i=0nCi Cn−i.C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}.

Remarks

With the definition of the node Catalan numbers, the statement holds by definition. Its content is in the combinatorial families that satisfy it. Example: C4=C0C3+C1C2+C2C1+C3C0=5+2+2+5=14C_4 = C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0 = 5 + 2 + 2 + 5 = 14. For Dyck words, the recurrence splits a word at the first return to level 00.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Catalan numbers, definition, no evidence levelCatalan numbersdefinitionCatalan recurrence, statement, no evidence levelCatalan recurrencestatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Catalan numbers definition
  2. Catalan recurrence statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Catalan_number, Properties
About this page
Tag0Y1MG9R5VN
URIm2://0Y1MG9R5VN
Kindstatement, theorem
WritingW0 stub
MSC05A15
StatusThis copy of the site has no build data. Run m2 status 0Y1MG9R5VN.
UsesCatalan numbers

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.