to a matching pair of parentheses, and its children are the nodes corresponding to the successive Dyck words within these parentheses. Leaf nodes correspond to empty parentheses: . In analogous fashion, we can construct a Dyck word from a rooted tree via a depth-first search. Thus, there is an isomorphism between Dyck words and rooted trees. In the above figures of lattice paths, each upward edge from the horizontal line at height to corresponds to an edge between node and its child. A node has as many children, as there are upward edges leading from the horizontal line at height . For example, in the first path for , the nodes and will have two children each; in the last (sixth) path, node will have three children and node will have one child. To construct a rooted tree from a lattice path and vice versa, we can employ an algorithm similar to the one mentioned the previous paragraph. As with Dyck words, there is an isomorphism between lattice paths and rooted trees. Partitions In the study of partitions, we see that in a set containing elements, we may partition that set in different ways, where is the th Bell number. Furthermore, the number of ways to partition a set into exactly blocks we use the Stirling numbers . Both of these concepts are a bit off-topic, but a necessary foundation for understanding the use of the Narayana numbers. In both of the above two notions crossing partitions are accounted for. To reject the crossing partitions and count only the non-crossing partitions, we may use the Catalan numbers to count the non-crossing partitions of all elements of the set, . To count the non-crossing partitions in which the set is partitioned in exactly blocks, we use the Narayana number . Generating function The generating function for the Narayana numbers is See also Catalan number Delannoy number Motzkin number Schröder number Pascal's triangle Citations References Triangles of numbers Integer sequences Factorial and binomial topics Permutations