Narayana Number

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

A closed-form expression of  is given by

where  is a binomial coefficient.

Summing over  gives the Catalan number

Enumerating  as a number triangle is called the Narayana triangle.

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.