Status: #good
Tags: #definition

Catalan numbers

The Catalan numbers are a combinatorial sequence that appears a lot in many different fields. They are given by the formula

There are many things that are counted by the Catalan numbers:

• Dyck path
• valid parenthesizations of $n+1$ letters (with proof here)
• complete binary trees with n+1 leaves
• plane binary trees with n vertices
• triangulations of a n+2 gon
• matchings of 2n vertices
• partitions of n vertices
• (permutation of length 3)-avoiding permutations
  • 2-queue sortable permutations
  • stack-sortable permutations of n items
• SYTs of shape (n, n)

Properties

Satisfies the recurrence relation: