Narayana number

In combinatorics, the Narayana numbers formula_1 form a triangular array of natural numbers, called the Narayana triangle, that occur in various counting problems. They are named after Canadian mathematician T. V. Narayana (1930–1987).
Formula.
The Narayana numbers can be expressed in terms of binomial coefficients:
Numerical values.
The first eight rows of the Narayana triangle read:
 "k" = 1 2 3 4 5 6 7 8
 "n" = 1 | 1
 2 | 1 1
 3 | 1 3 1
 4 | 1 6 6 1
 5 | 1 10 20 10 1
 6 | 1 15 50 50 15 1
 7 | 1 21 105 175 105 21 1
 8 | 1 28 196 490 490 196 28 1
Combinatorial interpretations.
Dyck words.
An example of a counting problem whose solution can be given in terms of the Narayana numbers formula_3, is the number of words containing pairs of parentheses, which are correctly matched (known as Dyck words) and which contain distinct nestings. For instance, formula_4, since with four pairs of parentheses, six sequences can be created which each contain two occurrences the sub-pattern :
 ()((())) (())(()) ((()))()
From this example it should be obvious that formula_5, since the only way to get a single sub-pattern is to have all the opening parentheses in the first positions, followed by all the closing parentheses. Also formula_6, as distinct nestings can be achieved only by the repetitive pattern .
More generally, it can be shown that the Narayana triangle is symmetric:
The sum of the rows in this triangle equal the Catalan numbers:
Monotonic lattice paths.
The Narayana numbers also count the number of lattice paths from formula_9 to formula_10, with steps only northeast and southeast, not straying below the -axis, with peaks.
The following figures represent the Narayana numbers formula_11, illustrating the above mentioned symmetries.
The sum of formula_11 is 1 + 6 + 6 + 1 = 14, which is the 4th Catalan number, formula_13. This sum coincides with the interpretation of Catalan numbers as the number of monotonic paths along the edges of an formula_14 grid that do not pass above the diagonal.
Rooted trees.
The number of unlabeled ordered rooted trees with formula_15 edges and formula_16 leaves is equal to formula_3.
This is analogous to the above examples:
Partitions.
In the study of partitions, we see that in a set containing elements, we may partition that set in formula_19 different ways, where formula_19 is the "th" Bell number. Furthermore, the number of ways to partition a set into exactly blocks we use the Stirling numbers formula_21. 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, formula_22. To count the non-crossing partitions in which the set is partitioned in exactly blocks, we use the Narayana number formula_3.
Generating function.
The generating function for the Narayana numbers is 