Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Narayana number
Summary
In combinatorics, the Narayana numbers form a triangular array of natural numbers, called the Narayana triangle, that occur in various counting problems. They are named after Canadian 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:
An example of a counting problem whose solution can be given in terms of the Narayana numbers , is the number of words containing n pairs of parentheses, which are correctly matched (known as Dyck words) and which contain k distinct nestings. For instance, , since with four pairs of parentheses, six sequences can be created which each contain two occurrences the sub-pattern :
(()(())) ((()())) ((())())
()((())) (())(()) ((()))()
From this example it should be obvious that , 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 , as n distinct nestings can be achieved only by the repetitive pattern .
More generally, it can be shown that the Narayana triangle is symmetric:
The sum of the rows in this triangle equal the Catalan numbers:
The Narayana numbers also count the number of lattice paths from to , with steps only northeast and southeast, not straying below the x-axis, with k peaks.
The following figures represent the Narayana numbers , illustrating the above mentioned symmetries.
The sum of is 1 + 6 + 6 + 1 = 14, which is the 4th Catalan number, . This sum coincides with the interpretation of Catalan numbers as the number of monotonic paths along the edges of an grid that do not pass above the diagonal.
The number of unlabeled ordered rooted trees with edges and leaves is equal to .
This is analogous to the above examples:
Each Dyck word can be represented as a rooted tree. We start with a single node – the root node. This is initially the active node. Reading the word from left to right, when the symbol is an opening parenthesis, add a child to the active a node and set this child as the active node.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.