Additional mathematical properties of Narayana numbers and Motzkin numbers

The work that follows in the lines below is, in gross, outcome of our work in observing and deriving inter-terms relation between Narayana numbers and their associated properties with Catalan numbers and Motzkin Numbers. Again Motzkin Numbers and its associated determinant and minors have hidden properties which is also explored giving proof in terms of theorems. To this, we have successively evolved inter connectivity among Motzkin numbers, Narayana Numbers and Catalan Numbers.

Illustrations explain the paper; they do not show study data.

AI-generated illustration

↗ Enlarge

Relationship between Combinatorial NumbersClose ×

AI-generated conceptual illustration (Geometric lattice paths on a coordinate grid). It explains the idea and does not show study data.

Open full-size image ↗

Introduction

The contents of this paper have triangularised division, though different but all assembled and are mutually interwoven. The first vertex, to some extent, prescribes some basic introduction to Catalan Numbers and describes our reframed work on the same. The second vertex deals with beautifully break-up of Catalan Numbers. These are Narayana Numbers, denoted as 𝑁(𝑛, 𝑘) with 𝑛, 𝑘 ∈ 𝑁 and 𝑛 ≥ 𝑘 with 1 ≤ 𝑘 ≤ 𝑛. These numbers are devotional to Catalan numbers but within each break-up such that their row wise sum for each value of 𝑛 and 𝑘 gives Catalan number. What we have designed is their row wise and column wise inter relation which helps harmonized composition of the table. The third and last in order is vertex with the label of Motzkin number which are strictly designed to follow some rules. Motzkin number (0, 0) to (n, 0), with some condition in a way that length of each segment of a path can be either 1 or √2. In addition to this, we have attempted to interpret planner graph associated with certain Motzkin Number. Also it is followed by some important properties.

Catalan Number 2.1 A brief introduction to our present work

Catalan Numbers are, as some call them superstitious numbers, backed by glorious beginning from the time of Chinese scientist Ming'antu (c. 1692c. 1763) who designed its pattern arising from geometrical construction. Along with the flow of time in 1751, Leonhard Euler, working on deriving the ways of triangulation of an (n+2)-gon found the result which we call Catalan Numbers. In this important work he was assisted by Christian Goldbach and more substantially by Johann Segner. Euler then observed that successive ratios have a pattern which can be given as

Segner, on further work on the same issue, derived the recurrence relation between Catalan numbers and derived that with,

It was the only time in 1838 when Belgium mathematician Charles Catalan, a tutor at Ecole Polytechnique, was inspired and devoted some years of life in the parallel type of work and proved the useful results.

The first one of its own type is

Following the same work he worked on same subject and perceived many applications in numerous real life situations. In this section, with the above brief notes we like to first put before our valued readers of what we have already done in our previous work. As a part of our previous paper [1] , what we have establish put below which may be noted and be used for the future purpose. These are as follows, where 𝑛, 𝑘 ∈ 𝑁, 1 ≤ 𝑘 ≤ 𝑛 and 𝑁(𝑛, 𝑘) is the k th Narayana number for a given n.

………. (4)

Each term for a fixed n and k under above restriction and confined to the following formula.

It is obvious from the above formula that N(n, 1) = 1 = N(n, n)

Narayana Number _ Tabular form

In this section we give a tabular form of N(n, k) for some initial values of 𝑛 ∈ 𝑁 and dependent value of parameter k,

Some Important Clues

A close look on the study of distribution of Narayana numbers we have been prompted to work in deriving some important clues.

As we know that for a given 𝑛 ≥ 1 and each

We are interested in investigating𝑁(𝑛, 𝑘 + 1) -𝑁(𝑛, 𝑘). This is the difference between values of two successive Narayana numbers for a given n and k.

Theorem 1

For a given system of Narayana numbers with above mentioned condition that 𝑛 ∈ 𝑁, 𝑛 ≥ 1, 𝑘 ∈ [1, 𝑛] we have 𝑁(𝑛, 𝑘 + 1) -𝑁(𝑛, 𝑘) = (𝑛 -1)! ( 𝑛 𝑘 ) [

In order to prove above equality we start with the definition of Narayana Numbers

In the same sequence we continue to establish one more theorem. This theorem aims at finding the difference between N(n+1, k) and N(n, k).

Theorem 2

In the notational terminology of Narayana numbers we will prove

L.H.S = 𝑁(𝑛 + 1, 𝑘) -𝑁(𝑛, 𝑘)

Theorem 3

Any Narayana Number N(n, k), 1 ≤ 𝑘 ≤ 𝑛 can be represented as a determinant of 2×2 Matrix 𝑀 𝑛 where Matrix 𝑀 𝑛 is as follows,

To give the proof of above statement we start with the definition of Narayana Numbers which can also be define as, 𝑁(𝑛, 𝑘) =

𝑁(𝑛, 𝑘

𝑁(𝑛, 𝑘

Targeting a Cell in Narayan Number Tabulation

The study of Narayana number table and its property lead us to two important properties aiming at particular cell and its neighborhood. These are as follows.

Using equations ( 6) and ( 7) one can also derive the formulae to find entry of each cell of the Narayana Triangle. In this section we also aimed to derive the same using two equations mentioned above. Using equation ( 6), we can write, ) ; 𝑘 = 0,1,2,3, … , 𝑛 -1 ………. (10)

Again, using equation ( 7)

Thus we have proved above results as stated; its importance lies in directly locating the cell value on a given value of 'n' and 'k'.

The difference results helps advancing from a given cell.

Motzkin Numbers and Determinant Properties

Pacing with Catalan number to some extent, geometrically we have another system known as Motzkin number system. They, in geometric nature, are the advancing path of 2n steps or n steps from (0, 0) to (n, n) of total length 2n or (0, 0) to (n, 0) of total length n as the corresponding case be Catalan number denoted as 𝐶 𝑛 or Motzkin number denoted as 𝑀 𝑛 . Some Motzkin Numbers are 1, 1, 2, 4, 9, 21, 51, 127… They satisfy the following recurrence relation,

𝑛-1 𝑘=𝑜

; 𝑛 ∈ 𝑁 and 𝑀 0 = 1 = 𝑀 1 ] and in general,

In connection to this we have two following properties stated in the form of theorems.

Theorem 4

To show that in above connection |𝑀 𝑛 | = 1 where 𝑀 𝑛 is given by ( 14) Proof: The proof is given by Principle of Mathematical Induction.

Part-1 for

We plug in Motzkin numbers and get

Part-2 We accept the result to hold true for 𝑛 = 𝑘 i.e. we accept the

Part-3 We establish the result for 𝑛 = 𝑘 + 1 i.e. we will show that 𝑀 𝑘+1 = 1

The first component on the RHS has a value zero while using the accepted result (15) of part-2, second component equals 1.

Therefore, 𝑀 𝑘+1 = 0 + 1 = 1 Thus the result is true for 𝑛 = 𝑘 + 1 and hence by Principle of Mathematical Induction we have 𝑀 𝑛 = 1, 𝑛 ≥ 1 without loss of generality.

Theorem 5

In the set of Motzkin rectangular array 𝑀 𝑛 , 𝑛 ≥ 2 we have the determinant value of minor of 𝑀 𝑜 (𝑀 𝑜 = 1) has always an order of the minor. This property can be established using the Principle of Mathematical Induction and properties of determinant.

Conclusion

As it happens in slim cases, we were inspired with certain units to be included in this segments and working on it have diversified in different areas connecting vertices, edges, and faces in Motzkin paths. This has widened our scope of research work leaving some open problems and to some extent these, with proven version, shall follow in the next research paper that will follow very shortly.

Figures and tables from the paper

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

Table text extracted from the original PDF; superscript letters are shown inline. The original table image is below.

View original table image

↗ Enlarge

Table 1Close ×

Table 1

Open full-size image ↗

Original paper tableSource PDF · page 2 ↗

↗ Enlarge

Table 2Close ×

Table 2

Open full-size image ↗

Original paper figureSource PDF · page 4 ↗

1. Mihir B Trivedi, Dr. Pradeep J Jha. Approaches differ: Catalan numbers. International Journal of Advanced Science and Research. 2017; 2(6):82-89.
2. Roy Oste, Joris Van der Jeugt. Motzkin paths, Motzkin polynomials and recurrence Relations, 2015.
3. Paul Berry. A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations. Journal of Integer Sequences. 2011, 14, Article 11.3.8.
4. Tom Davis. Catalan Numbers, 2016.
5. Donaghey R, Shapiro LW. Motzkin numbers. J. Comb. Theory A. 1977; 23:291-301.