Narayana number

In combinatorics, the Narayana numbers N(n, k), n = 1, 2, 3 ..., 1 ≤ k ≤ n, form a triangular array of natural numbers, called Narayana triangle, that occur in various counting problems. They are named after Indian mathematician T. V. Narayana (1930–1987).

The Narayana numbers can be expressed in terms of binomial coefficients:

The first eight rows of the Narayana triangle read:

(sequence in the OEIS)

An example of a counting problem whose solution can be given in terms of the Narayana numbers N(n, k), is the number of expressions containing n pairs of parentheses, which are correctly matched and which contain k distinct nestings. For instance, N(4, 2) = 6 as with four pairs of parentheses six sequences can be created which each contain two times the sub-pattern '()':

From this example it should be obvious that N(n, 1) = 1, since the only way to get a single sub-pattern '()' is to have all the opening parentheses in the first n positions, followed by all the closing parentheses. Also N(n, n) = 1, as distinct nestings can be achieved only by the repetitive pattern ()()() ... (). More generally, it can be shown that the Narayana triangle is symmetric: N(n, k) = N(n, n − k + 1).

The sum of the rows in this triangle equal the Catalan numbers:

To illustrate this relationship, the Narayana numbers also count the number of paths from (0, 0) to (2n, 0), with steps only northeast and southeast, not straying below the x-axis, with k peaks.

The following figures represent the Narayana numbers N(4, k):

The sum of N(4, k) is 1 + 6 + 6 + 1, or 14, which is the same as Catalan number C₄. This sum coincides with the interpretation of Catalan numbers as the number of monotonic paths along the edges of an n × n grid that do not pass above the diagonal.

In the study of partitions, we see that in a set containing n elements, we may partition that set in ${\displaystyle B_{n}}$ different ways, where ${\displaystyle B_{n}}$ is the n^th Bell number. Furthermore, the number of ways to partition a set into exactly k blocks we use the Stirling numbers ${\displaystyle S(n,k)}$. 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.

...
Wikipedia