Narayana number

In combinatorics, the Narayana numbers N(n, k), n = 1, 2, 3 ..., 1 ≤ k ≤ n, form a triangular array of natural numbers, called Narayana triangle, that occur in various counting problems. They are named after Indian mathematician T. V. Narayana (1930–1987).

Formula

The Narayana numbers can be expressed in terms of binomial coefficients:

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

Numerical values

The first eight rows of the Narayana triangle read:

k =      1   2   3   4   5   6   7   8
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
    7    1  21 105 175 105  21   1
    8    1  28 196 490 490 196  28   1

(sequence A001263 in OEIS)

Combinatorial interpretations

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

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:
N(4, 2) = 6 paths with 2 peaks:
N(4, 3) = 6 paths with 3 peaks:
N(4, 4) = 1 path with 4 peaks:

The sum of N(4, k) is 1 + 6 + 6 + 1, or 14, which is the same as Catalan number C₄. 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.

Partitions

The 1,6,6,1 noncrossing partitions with 1,2,3,4 blocks of a 4-element set

In the study of partitions, we see that in a set containing n elements, we may partition that set in $B_n$ different ways, where $B_n$ is the n^th Bell number. Furthermore, the number of ways to partition a set into exactly k blocks we use the Stirling numbers $S(n,k)$ . 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 noncrossing partitions, we may use the Catalan numbers to count the non-crossing partitions of all n elements of the set, $C_n$ . To count the non-crossing partitions in which the set is partitioned in exactly k blocks, we use the Narayana number $N(n,k)$ .

References

P. A. MacMahon (1915–1916). Combinatorial Analysis. Cambridge University Press.
T. K. Petersen (2015). "Narayana numbers" (PDF). Eulerian Numbers. Basel: Birkhäuser. doi:10.1007/978-1-4939-3091-3.

Classes of natural numbers

Powers and
related numbers

Of the form
a × 2^b ± 1

Other polynomial
numbers

Recursively defined
numbers

Possessing a
specific set
of other numbers

Expressible via
specific sums

Generated
via a sieve

Lucky

Code related

Meertens

Figurate numbers

2-dimensional

centered	Centered triangular Centered square Centered pentagonal Centered hexagonal Centered heptagonal Centered octagonal Centered nonagonal Centered decagonal Star

non-centered	Triangular Square Square triangular Pentagonal Hexagonal Heptagonal Octagonal Nonagonal Decagonal Dodecagonal

3-dimensional

centered	Centered tetrahedral Centered cube Centered octahedral Centered dodecahedral Centered icosahedral

non-centered	Tetrahedral Octahedral Dodecahedral Icosahedral Stella octangula

pyramidal	Square pyramidal Pentagonal pyramidal Hexagonal pyramidal Heptagonal pyramidal

4-dimensional

centered	Centered pentachoric Squared triangular

non-centered	Pentatope

Pseudoprimes

Combinatorial
numbers

Arithmetic functions

By properties of σ(n)	Abundant Almost perfect Arithmetic Colossally abundant Descartes Hemiperfect Highly abundant Highly composite Hyperperfect Multiply perfect Perfect Practical number Primitive abundant Quasiperfect Refactorable Sublime Superabundant Superior highly composite Superperfect

By properties of Ω(n)	Almost prime Semiprime

By properties of φ(n)	Highly cototient Highly totient Noncototient Nontotient Perfect totient Sparsely totient

By properties of s(n)	Amicable Betrothed Deficient Semiperfect

Dividing a quotient

Other prime factor
or divisor related
numbers

Recreational
mathematics

Base-dependent
numbers

This article is issued from Wikipedia - version of the Wednesday, December 16, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.