TOPICS
Search

Narayana Number


The Narayan number N(n,k) for n=1, 2, ... and k=1, ..., n gives a solution to several counting problems in combinatorics. For example, N(n,k) gives the number of expressions with n pairs of parentheses that are correctly matched and contain k distinct nestings. It also gives the number Dyck paths of length n with exactly k peaks.

A closed-form expression of N(n,k) is given by

 N(n,k)=1/n(n; k)(n; k-1),

where (n; k) is a binomial coefficient.

Summing over k gives the Catalan number

 C_n=sum_(k=1)^nN(n,k).

Enumerating N(n,k) as a number triangle is called the Narayana triangle.


See also

Catalan Number, Dyck Path, Narayana Triangle

Explore with Wolfram|Alpha

References

MacMahon, P. A. Combinatory Analysis, 2 vols. New York: Chelsea, 1960.Narayana, T. V. Lattice Path Combinatorics with Statistical Applications. Toronto, Canada: University of Toronto Press, pp. 100-101, 1979.Stanley, R. P. Problems 6.36(a) and (b) in Enumerative Combinatorics, Vol. 2. Cambridge, England: Cambridge University Press, 1999.

Referenced on Wolfram|Alpha

Narayana Number

Cite this as:

Weisstein, Eric W. "Narayana Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NarayanaNumber.html

Subject classifications