Math 2.0

Combinatorics Theorem

Dyck words are counted by Catalan numbers

Builds on Catalan numbersDyck word

Statement

Let nn be a natural number. Then the number of Dyck words of semilength nn is the Catalan number CnC_n.

Remarks

For n=3n = 3 the 55 Dyck words are UUUDDDUUUDDD, UUDUDDUUDUDD, UUDDUDUUDDUD, UDUUDDUDUUDD and UDUDUDUDUDUD. Proof idea: a nonempty Dyck word has a unique form Uw1Dw2U w_1 D w_2, where w1w_1 and w2w_2 are Dyck words. This gives the Catalan recurrence.

Reading path

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

Show the path as a graph
Catalan numbers, definition, no evidence levelCatalan numbersdefinitionDyck word, definition, no evidence levelDyck worddefinitionDyck words are counted by Catalan numbers, statement, no evidence levelDyck words are counte…statement
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. Dyck word definition
  3. Dyck words are counted by Catalan numbers statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Catalan_number, Applications in combinatorics
About this page
Tag017SRZ7NE9
URIm2://017SRZ7NE9
Kindstatement, theorem
WritingW0 stub
MSC05A15
StatusThis copy of the site has no build data. Run m2 status 017SRZ7NE9.
UsesCatalan numbers, Dyck word

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.