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:

N(n,k) = \frac{1}{n}{n\choose k}{n\choose k-1}.

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).

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

(sequence A001263 in OEIS)

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

N(n,1) + N(n,2) + N(n,3) + \cdots + N(n,n) = C_n.

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: Image:Narayana41.svg
N(4, 2) = 6 paths with 2 peaks: Image:Narayana42.svg
N(4, 3) = 6 paths with 3 peaks: Image:Narayana43.svg
N(4, 4) = 1 path with 4 peaks: Image:Narayana44.svg

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).