Narayana number
From Wikipedia, the free encyclopedia
In combinatorics, the Narayana numbers N(n, k), n = 1, 2, 3 ..., 1 ≤ k ≤ n, form a triangle of natural numbers, called Narayana triangle, that occur in various counting problems. They are named for T.V. Narayana, a mathematician from India.
The Narayana numbers can be expressed in terms of binomial coefficients:
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 first six rows of the Narayana triangle read:
k = 1 2 3 4 5 6
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
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):
| N(4, k) | Paths |
|---|---|
| N(4, 1) = 1 path with 1 peak: |  |
| N(4, 2) = 6 paths with 2 peaks: |  |
| N(4, 3) = 6 paths with 3 peaks: |  |
| N(4, 4) = 1 path with 4 peaks: |  |
The sum of N(4, k) is 1 + 6 + 6 + 1, or 14, which is the same as Catalan number C4. 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.
[edit] See also
[edit] References
- P. A. MacMahon, Combinatorial Analysis, Vols. 1 and 2, Cambridge University Press (1915, 1916).
