Narayana Numbers

The Narayana numbers N(n, k) describe, among other things, the number of paths from (0, 0) to (2n, 0) that stay above the x-axis, using only steps northeast and southeast, having k peaks.

For example, N(1, 1) = 1, since there’s only one such path and it has one peak:

N(1, 1) = 1

Likewise, N(2, 1) = 1 and N(2, 2) = 1, since there are two paths from (0, 0) to (4, 0); the first has one peak and the second has two peaks:

N(2, 1) = N(2, 2) = 1

Here, N(3, 1) = 1; N(3, 2) = 3 [that is, there are three paths that have 2 peaks]; and N(3, 3) = 1.

N(3, k)

Paths for N(4, k):

N(4, k)

From these, we see that N(n, 1) = 1 and N(n, n) = 1.

The totals of N(n, k) as k goes from 1 to n are the Catalan numbers, as is apparent from the path interpretation.

Copyright © 1998–2017 by Robert Dickau.

[ home ] || [ 2011-02-20 ]


www.robertdickau.com/narayana.html