Thursday, 23 March 2023

Motzkin Numbers

I recently came upon a class of numbers known as Motzkin numbers. They are defined as follows:

In mathematics, the n-th Motzkin number is the number of different ways of drawing non-intersecting chords between n points on a circle. Source.

Figures 1 and 2 are illustrations showing two of the numbers (9 and 21) using the same source:

Figure 1: there are 9 ways to draw non-intersecting chords
between 4 points on a circle (M(4)= 9)

Figure 2: there are 21 ways to draw non-intersecting chords
between 5 points on a circle (M(5) = 21)

The Motzkin numbers satisfy the following recurrence relation:$$M_n = \frac{2n+1}{n+2} M_{n-1}+\frac{3n-3}{n+2} M_{n-2}$$The Motzkin numbers can be expressed in terms of binomial coefficients and Catalan numbers:$$M_n=\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{2k} C_k\\ C_{n+1}=\sum_{k=0}^n \binom{n}{k} M_k$$The generating function for the Motzkin numbers is given by:$$ \frac{1-x-\sqrt{1-2x-3x^2} }{2x^2}$$I asked ChatGPT about them.

Q: Can you explain what Motzkin numbers are and give some simple examples of their usefulness.

A: Motzkin numbers, named after the mathematician Theodor Motzkin, are a sequence of numbers that count the number of ways to draw non-intersecting chords between n points on a circle. They are denoted by M(n).

The first few Motzkin numbers are:

M(0) = 1, M(1) = 1, M(2) = 2, M(3) = 4, M(4) = 9, M(5) = 21, M(6) = 51, M(7) = 127, M(8) = 323, M(9) = 835, M(10) = 2188

Motzkin numbers have a variety of applications in combinatorics, algebraic geometry, and physics. Here are some simple examples of their usefulness:

  • Counting lattice paths: A lattice path is a path on a grid of integer points. The number of lattice paths from (0, 0) to (n, k) that only move up, down, or diagonally up and to the right, and never below the x-axis, is given by the Motzkin number M(k). 

  • Counting RNA structures: RNA is a molecule that plays a key role in protein synthesis. The number of possible secondary structures for an RNA molecule of length n is given by the Motzkin number M(-1). 

  • Counting balanced chemical reactions: The number of balanced chemical reactions involving n molecules is given by the Motzkin number M(-1). This can be useful in chemistry and chemical engineering. 

  • Counting irreducible algebraic curves: An irreducible algebraic curve is a curve that cannot be expressed as the union of two smaller curves. The number of irreducible algebraic curves of degree n in projective space is given by the Motzkin number M(-1). 

  • Counting diagrams in knot theory: Knot theory is the study of mathematical knots. The number of diagrams that represent a knot with n crossings is given by the Motzkin number M(-2).

These are just a few examples of the many applications of Motzkin numbers in various fields of mathematics and science.

The Motzkin numbers constitute OEIS A001006:


 A001006

Motzkin
 numbers: number of ways of drawing any number of non-intersecting chords joining \(n\) (labeled) points on a circle.



The first few members, up to one million, are:

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467

The problem from the perspective of my diurnal age is that the last member occurred when I was 15511 days old and the next will occur if I were to reach 41835 days old, which is highly unlikely. I'm currently 27017 days old and a few days away from my 74th birthday. However, if reflections and rotations are allowed since, returning to Figures 1 and 2, the number 9 becomes 4 and the number 21 becomes 5. These are noticeably smaller.

These unlabeled Motzkin numbers constitute OEIS A175954:


 A175954

Unlabeled (cyclic) Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n unlabeled points equally spaced on a circle, up to rotations of the circle.


The initial members, up to one million, are:

1, 1, 2, 2, 4, 5, 12, 19, 46, 95, 230, 528, 1320, 3219, 8172, 20714, 53478, 138635, 363486, 957858

However, these numbers again miss my possible forthcoming diurnal ages as there is a jump from 20714 to 53478. Ah well.

No comments:

Post a Comment