Editing Catalan number (section)

== Applications in combinatorics ==

There are many counting problems in [[combinatorics]] whose solution is given by the Catalan numbers. The book ''Enumerative Combinatorics: Volume 2'' by combinatorialist [[Richard P. Stanley]] contains a set of exercises which describe 66 different interpretations of the Catalan numbers. Following are some examples, with illustrations of the cases {{math|1=''C''<sub>3</sub> = 5}} and {{math|1=''C''<sub>4</sub> = 14}}.

[[File:Dyck lattice D4.svg|thumb|Lattice of the 14 Dyck words of length 8 – {{mvar|(}} and {{mvar|)}} interpreted as ''up'' and ''down'']]
* {{math|''C''<sub>''n''</sub>}} is the number of [[Dyck word]]s<ref>[https://www.findstat.org/CollectionsDatabase/Cc0005/ Dyck paths]</ref> of length {{math|2''n''}}. A Dyck word is a [[string (computer science)|string]] consisting of {{mvar|n}} X's and {{mvar|n}} Y's such that no initial segment of the string has more Y's than X's. For example, the following are the Dyck words up to length 6:
<div class="center"><big> XY</big></div>
<div class="center"><big> XXYY &nbsp;&nbsp;&nbsp; XYXY</big></div>
<div class="center"><big> XXXYYY &nbsp;&nbsp;&nbsp; XYXXYY &nbsp;&nbsp;&nbsp; XYXYXY &nbsp;&nbsp;&nbsp; XXYYXY &nbsp;&nbsp;&nbsp; XXYXYY</big></div>
* Re-interpreting the symbol X as an open [[Bracket#Parentheses|parenthesis]] and Y as a close parenthesis, {{math|''C''<sub>''n''</sub>}} counts the number of expressions containing {{mvar|n}} pairs of parentheses which are correctly matched:
<div class="center"><big> ((())) &nbsp;&nbsp;&nbsp; (()())  &nbsp;&nbsp;&nbsp; (())() &nbsp;&nbsp;&nbsp; ()(()) &nbsp;&nbsp;&nbsp; ()()()  </big></div>
* {{math|''C''<sub>''n''</sub>}} is the number of different ways {{math|''n'' + 1}} factors can be completely [[bracket|parenthesized]] (or the number of ways of [[associativity|associating]] {{mvar|n}} applications of a [[binary operator]], as in the [[matrix chain multiplication]] problem). For {{math|1=''n'' = 3}}, for example, we have the following five different parenthesizations of four factors:
<div class="center"><big>((ab)c)d &nbsp;&nbsp;&nbsp; (a(bc))d &nbsp;&nbsp;&nbsp; (ab)(cd) &nbsp;&nbsp;&nbsp; a((bc)d) &nbsp;&nbsp;&nbsp; a(b(cd))</big></div>
* Successive applications of a binary operator can be represented in terms of a [[Binary tree#Types of binary trees|full binary tree]], by labeling each leaf {{math|''a'', ''b'', ''c'', ''d''}}. It follows that {{math|''C''<sub>''n''</sub>}} is the number of full binary [[tree (graph theory)|trees]] with {{math|''n'' + 1}} leaves, or, equivalently, with a total of {{mvar|n}} internal nodes:
[[Image:Catalan 4 leaves binary tree example.svg|center]]
[[File:Tamari lattice, trees.svg|thumb|The [[associahedron]] of order 4 with the C<sub>4</sub>=14 full binary trees with 5 leaves]]
* {{math|''C''<sub>''n''</sub>}} is the number of non-isomorphic [[Tree (graph theory)#Plane tree|ordered (or plane) trees]] with {{math|''n'' + 1}} vertices.<ref>Stanley p.221 example (e)</ref> See [[Binary tree#Encoding general trees as binary trees|encoding general trees as binary trees]]. For example, {{math|''C''<sub>''n''</sub>}} is the number of possible [[Parse tree|parse trees]] for a sentence (assuming binary branching), in natural language processing.
* {{math|''C''<sub>''n''</sub>}} is the number of monotonic [[lattice path]]s along the edges of a grid with {{math|''n'' × ''n''}} square cells, which do not pass above the diagonal. A monotonic path is one which starts in the lower left corner, finishes in the upper right corner, and consists entirely of edges pointing rightwards or upwards. Counting such paths is equivalent to counting Dyck words: X stands for "move right" and Y stands for "move up".

The following diagrams show the case {{math|1=''n'' = 4}}:
[[Image:Catalan number 4x4 grid example.svg|450px|center]]
This can be represented by listing the Catalan elements by column height:<ref>{{cite journal|last1=Črepinšek|first1=Matej|last2=Mernik|first2=Luka|title=An efficient representation for solving Catalan number related problems|journal=International Journal of Pure and Applied Mathematics|year=2009|volume=56|issue=4|pages = 589–604|url=http://www.ijpam.eu/contents/2009-56-4/11/11.pdf}}</ref>

[[File:Tamari lattice, hexagons.svg|thumb|The dark triangle is the root node, the light triangles correspond to internal nodes of the binary trees, and the green bars are the leaves.]]

 <div style="text-align: center;">[0,0,0,0] [0,0,0,1] [0,0,0,2] [0,0,1,1]</div>

 <div style="text-align: center;">[0,1,1,1] [0,0,1,2] [0,0,0,3] [0,1,1,2] [0,0,2,2] [0,0,1,3]</div>

 <div style="text-align: center;">[0,0,2,3] [0,1,1,3] [0,1,2,2] [0,1,2,3]</div>

* A [[convex polygon]] with {{math|''n'' + 2}} sides can be cut into [[triangle]]s by connecting vertices with non-crossing [[line segment]]s (a form of [[polygon triangulation]]). The number of triangles formed is {{mvar|n}} and the number of different ways that this can be achieved is {{math|''C''<sub>''n''</sub>}}. The following hexagons illustrate the case {{math|1=''n'' = 4}}:
[[Image:Catalan-Hexagons-example.svg|400px|center]]
* {{math|''C''<sub>''n''</sub>}} is the number of [[Stack (data structure)|stack]]-sortable [[permutation]]s of {{math|{{mset|1, ..., ''n''}}}}. A permutation {{mvar|w}} is called [[stack-sortable permutation|stack-sortable]] if {{math|1=''S''(''w'') = (1, ..., ''n'')}}, where {{math|''S''(''w'')}} is defined recursively as follows: write {{math|1=''w'' = ''unv''}} where {{mvar|n}} is the largest element in {{mvar|w}} and {{mvar|u}} and {{mvar|v}} are shorter sequences, and set {{math|1=''S''(''w'') = ''S''(''u'')''S''(''v'')''n''}}, with {{mvar|S}} being the identity for one-element sequences.
* {{math|''C''<sub>''n''</sub>}} is the number of permutations of {{math|{{mset|1, ..., ''n''}}}} that avoid the [[permutation pattern]]&nbsp;123 (or, alternatively, any of the other patterns of length 3); that is, the number of permutations with no three-term increasing subsequence.  For {{math|1=''n'' = 3}}, these permutations are 132, 213, 231, 312 and 321.  For {{math|1=''n'' = 4}}, they are 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 and 4321.
* {{math|''C''<sub>''n''</sub>}} is the number of [[noncrossing partition]]s of the set {{math|{{mset|1, ..., ''n''}}}}. [[A fortiori argument|''A fortiori'']], {{math|''C''<sub>''n''</sub>}} never exceeds the {{mvar|n}}-th [[Bell number]].  {{math|''C''<sub>''n''</sub>}} is also the number of noncrossing partitions of the set {{math|{{mset|1, ..., 2''n''}}}} in which every block is of size 2.
* {{math|''C''<sub>''n''</sub>}} is the number of ways to tile a stairstep shape of height {{mvar|n}} with {{mvar|n}} rectangles. Cutting across the anti-diagonal and looking at only the edges gives full binary trees. The following figure illustrates the case {{math|1=''n'' = 4}}:
[[File:Catalan stairsteps 4.svg|400px|center]]
* {{math|''C''<sub>''n''</sub>}} is the number of ways to form a "mountain range" with {{mvar|n}} upstrokes and {{mvar|n}} downstrokes that all stay above a horizontal line. The mountain range interpretation is that the mountains will never go below the horizon.
<div align="center">
{| class="wikitable
|+ Mountain Ranges
|-
| <math>n = 0:</math>
| style="font-family:monospace;" |*
| 1 way
|-
| <math>n = 1:</math>
| style="font-family:monospace;" |/\
| 1 way
|-
| <math>n = 2:</math>
| style="font-family:monospace;" |{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}/\<br />/\/\,{{0}}/{{0}}{{0}}\
|2 ways
|-
| <math>n = 3:</math>
| style="font-family:monospace;" |{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}/\<br />{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}/\{{0}}{{0}}{{0}}{{0}}/\{{0}}{{0}}{{0}}{{0}}{{0}}{{0}}/\/\{{0}}{{0}}{{0}}{{0}}/{{0}}{{0}}\<br />/\/\/\,{{0}}/\/{{0}}{{0}}\,{{0}}/{{0}}{{0}}\/\,{{0}}/{{0}}{{0}}{{0}}{{0}}\,{{0}}/{{0}}{{0}}{{0}}{{0}}\
|5 ways
|}
</div>
* {{math|''C''<sub>''n''</sub>}} is the number of [[Young tableau#Tableaux|standard Young tableaux]] whose diagram is a 2-by-{{mvar|n}} rectangle. In other words, it is the number of ways the numbers {{math|1, 2, ..., 2''n''}} can be arranged in a 2-by-{{mvar|n}} rectangle so that each row and each column is increasing. As such, the formula can be derived as a special case of the [[Young tableau#Dimension of a representation|hook-length formula]].
<pre>
123   124   125   134   135
456   356   346   256   246
</pre>
* <math>C_n</math> is the number of length {{mvar|n}} sequences  that start with <math>1</math>, and can increase by either <math>0</math> or <math>1</math>, or decrease by any number (to at least <math>1</math>). For <math>n=4</math> these are <math>1234, 1233, 1232, 1231, 1223, 1222, 1221, 1212, 1211, 1123, 1122, 1121, 1112, 1111</math>. From a Dyck path, start a counter at {{math|0}}. An X increases the counter by {{math|1}} and a Y decreases it by {{math|1}}. Record the values at only the X's. Compared to the similar representation of the [[Bell number#Rhyme schemes|Bell numbers]], only <math>1213</math> is missing.