View source for Narayana number

{{Short description|Triangular array of natural numbers}}
{{Infobox integer sequence
| named_after = Tadepalli Venkata Narayana
| terms_number = [[infinity]]
| formula = <math>\operatorname{N}(n, k) = \frac{1}{n} {n \choose k} {n \choose k-1}</math>
| OEIS = A001263
| OEIS_name = Triangle of Narayana 
}}
In [[combinatorics]], the '''Narayana numbers''' <math>\operatorname{N}(n, k), n \in \mathbb{N}^+, 1 \le k \le n</math> form a [[triangular array]] of [[natural number]]s, called the '''Narayana triangle,''' that occur in various [[Combinatorial enumeration|counting problems]]. They are named after Canadian mathematician [[Tadepalli Venkata Narayana|T. V. Narayana (1930–1987)]].

== Formula ==
The Narayana numbers can be expressed in terms of [[binomial coefficient]]s:

: <math>\operatorname{N}(n, k) = \frac{1}{n} {n \choose k} {n \choose k-1}</math>

== Numerical values ==
The first eight rows of the Narayana triangle read:

{| class=wikitable style="text-align:right;"
|-
! rowspan=2 | ''n''
! colspan=8 | ''k''
|-
! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8
|-
! 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
|-
! 7
| 1 || 21 || 105 || 175 || 105 || 21 || 1
|-
! 8
| 1 || 28 || 196 || 490 || 490 || 196 || 28 || 1
|}
{{OEIS|id=A001263}}

== Combinatorial interpretations ==

=== Dyck words ===

An example of a counting problem whose solution can be given in terms of the Narayana numbers <math>\operatorname{N}(n, k)</math>, is the number of words containing {{tmath|n}} pairs of parentheses, which are correctly matched (known as [[Dyck word]]s) and which contain {{tmath|k}} distinct nestings. For instance, <math>\operatorname{N}(4, 2) = 6</math>, since with four pairs of parentheses, six sequences can be created which each contain two occurrences the sub-pattern {{code|()}}:

 (()(()))  ((()()))  ((())())
 ()((()))  (())(())  ((()))()

From this example it should be obvious that <math>\operatorname{N}(n, 1) = 1</math>, since the only way to get a single sub-pattern {{code|()}} is to have all the opening parentheses in the first {{tmath|n}} positions, followed by all the closing parentheses. Also <math>\operatorname{N}(n, n) = 1</math>, as {{tmath|n}} distinct nestings can be achieved only by the repetitive pattern {{code|()()()…()}}.

More generally, it can be shown that the Narayana triangle is symmetric:

:<math>\operatorname{N}(n, k) = \operatorname{N}(n, n-k+1)</math>

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

:<math>\operatorname{N}(n, 1) + \operatorname{N}(n, 2) + \operatorname{N}(n, 3) + \cdots + \operatorname{N}(n, n) = C_n</math>

=== Monotonic lattice paths ===

The Narayana numbers also count the number of [[Lattice path|lattice paths]] from <math>(0, 0)</math> to <math>(2n, 0)</math>, with steps only northeast and southeast, not straying below the {{mvar|x}}-axis, with {{tmath|k}} peaks.

The following figures represent the Narayana numbers <math>\operatorname{N}(4, k)</math>, illustrating the above mentioned symmetries.

{| class="wikitable"
|-
! <math>\operatorname{N}(4, k)</math>
! Paths
|-
| ''N''(4,&nbsp;1) = '''1''' path with 1 peak
| [[File:Narayana N(4, 1).svg]]
|-
| ''N''(4,&nbsp;2) = '''6''' paths with 2 peaks:
| [[File:Narayana N(4, 2).svg]]
|-
| ''N''(4,&nbsp;3) = '''6''' paths with 3 peaks:
| [[File:Narayana N(4, 3).svg]]
|-
| ''N''(4,&nbsp;4) = '''1''' path with 4 peaks:
| [[File:Narayana N(4, 4).svg]]
|}

The sum of <math>\operatorname{N}(4, k)</math> is 1 + 6 + 6 + 1 = 14, which is the 4th Catalan number, <math>C_4</math>. This sum coincides with the interpretation of Catalan numbers as the number of monotonic paths along the edges of an <math>n \times n</math> grid that do not pass above the diagonal.

=== Rooted trees ===

[[File:Unlabeled ordered rooted trees of 4 edges and 2 leaves.svg|thumb|The 6 ordered rooted trees of 4 edges and 2 leaves, corresponding to the Narayana number N(4, 2)]]

The number of unlabeled [[Tree_(graph_theory)#Ordered_tree|ordered]] [[Tree_(graph_theory)#Rooted_tree|rooted]] trees with <math>n</math> edges and <math>k</math> leaves is equal to <math>\operatorname{N}(n, k)</math>.

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 node and set this child as the active node. When the symbol is a closing parenthesis, set the parent of the active node as the active node. This way we obtain a tree, in which every non-root node corresponds to a matching pair of parentheses, and its children are the nodes corresponding to the successive Dyck words within these parentheses. Leaf nodes correspond to empty parentheses: {{code|()}}. In analogous fashion, we can construct a Dyck word from a rooted tree via a depth-first search. Thus, there is an isomorphism between Dyck words and rooted trees.

* In the above figures of lattice paths, each upward edge from the horizontal line at height {{tmath|y}} to {{tmath|y}}{{tmath|+1}} corresponds to an edge between node {{tmath|y}} and its child. A node {{tmath|y}} has as many children, as there are upward edges leading from the horizontal line at height {{tmath|y}}. For example, in the first path for <math>\operatorname{N}(4, 3)</math>, the nodes {{math|0}} and {{math|1}} will have two children each; in the last (sixth) path, node {{math|0}} will have three children and node {{math|1}} will have one child. To construct a rooted tree from a lattice path and vice versa, we can employ an algorithm similar to the one mentioned the previous paragraph. As with Dyck words, there is an isomorphism between lattice paths and rooted trees.

== Partitions ==
[[File:Noncrossing partitions 4; Hasse.svg|thumb|The 1,6,6,1 [[non-crossing partition]]s with 1,2,3,4 blocks of a 4-element set]]
In the study of partitions, we see that in a set containing {{tmath|n}} elements, we may partition that set in <math>B_n</math> different ways, where <math>B_n</math> is the {{tmath|n}}''<sup>th</sup>'' [[Bell number]]. Furthermore, the number of ways to partition a set into exactly {{tmath|k}} blocks we use the [[Stirling numbers of the second kind|Stirling number]]s <math>S(n, k)</math>. Both of these concepts are a bit off-topic, but a necessary foundation for understanding the use of the Narayana numbers. In both of the above two notions crossing partitions are accounted for.

To reject the crossing partitions and count only the [[non-crossing partition]]s, we may use the [[Catalan number]]s to count the non-crossing partitions of all {{tmath|n}} elements of the set, <math>C_n</math>.  To count the non-crossing partitions in which the set is partitioned in exactly {{tmath|k}} blocks, we use the Narayana number <math>\operatorname{N}(n, k)</math>.

== Generating function ==
The generating function for the Narayana numbers is {{sfn|Petersen|2015|p=25}}
:<math>
\sum_{n=1}^\infty \sum_{k=1}^n \operatorname{N}(n, k) z^n t^{k-1} = \frac{1-z(t+1) - \sqrt{1-2z(t+1)+z^2(t-1)^2}}{2tz} \;.
</math>
<!--
  Petersen is indexing the k from 0 to n-1.
  Petersen also puts a "1" in for the constant term, by defining C_0(t)=1 and then summing from n=0.
-->

==See also==
* [[Catalan number]]
* [[Delannoy number]]
* [[Motzkin number]]
* [[Narayana polynomials]]
* [[Schröder number]]
* [[Pascal's triangle]]
* {{Wikiversity-inline|Partition related number triangles}}

==Citations==
{{reflist}}

==References==
* {{cite book |author=P. A. MacMahon |title=Combinatorial Analysis |publisher=Cambridge University Press |year=1915–1916}}
* {{cite book |first=T. Kyle | last = Petersen |chapter=Narayana numbers |title=Eulerian Numbers | series = Birkhäuser Advanced Texts Basler Lehrbücher |publisher=Birkhäuser |place=Basel |year=2015 |chapter-url=https://www.springer.com/cda/content/document/cda_downloaddocument/9781493930906-c1.pdf |doi=10.1007/978-1-4939-3091-3 | isbn = 978-1-4939-3090-6 }}

{{Classes of natural numbers}}

[[Category:Eponymous numbers in mathematics]]
[[Category:Triangles of numbers]]
[[Category:Integer sequences]]
[[Category:Factorial and binomial topics]]
[[Category:Permutations]]