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(n -1). 

• Counting balanced chemical reactions: The number of balanced chemical reactions involving n molecules is given by the Motzkin number M(n -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(n -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(n -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.

Sum of Squares of Integers and Catalan Numbers

As I began reading a new book Catalan Numbers With Applications by Thomas Koshy, I hadn't progressed far before I came across the statement:$$ \sum_{k=1}^n k^2=\frac{n(n+1)(2n+1)}{6}$$At this point, I had to pause because the author had just assumed this result but I couldn't see how to prove it. I needed to do a little digging but before long I came across an interesting proof of the result on this site. The website starts slowly and works out firstly what the sum of the first n integers will be. Here is how it is worked out: $$ \begin{align} (k-1)^2&=k^2-2k+1\\ \text{Rearranging the terms as below:}\\k^2-(k-1)^2&=2k-1\\ \text{Now sum both sides:}\\ \sum_{k=1}^n (k^2-(k-1)^2)&=2 \sum_{k=1}^n k-\sum_{k=1}^n 1\\n^2&=2S_n-n\\S_n&=\frac{n^2+n}{2}\\&=\frac{n(n+1)}{2} \end{align} $$ After this the website goes on to tackle the sum of the squares of the first n integers as follows (using a similar approach): $$\begin{align} (k-1)^3&=k^3-3k^2+3k+1\\ \text{Rearrange the terms: }\\k^3-(k-1)^3&=3k^2-3k-1\\ \text{Summing both sides:}\\ \sum_{k=1}^n (k^3-(k-1)^3)&=3 \sum_{k=1}^n k^2-3 \sum_{k=1}^n k -\sum_{k=1}^n 1\\n^3&=3 \sum_{k=1}^n k^2 -3 \frac{n(n+1)}{2}-n \\ \sum_{k=1}^n k^2&=\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n\\&=\frac{n(n+1)(2n+1)}{6} \end{align}$$ The website then goes on to establish a general result for the sum of integers raised to any power. The question is asked is there a formula for calculating: $$ 1^a+2^a+3^a+ \cdots + (n-1)^a + n^a=\sum_{k=1}^n k^a \text{ ?} $$Well there is, it's called Faulhaber's Formula and involves Bernoulli numbers but I won't go into that here.

For now, I can go on reading my book about the Catalan numbers. I first made a blog post about Catalan numbers back in 2015 on Tuesday the 29th September. This was the first time I'd really heard of them and I didn't delve deeply into them at all in that post. Hopefully I'll have more to say in later posts about these numbers.

The Catalan numbers are of the form: \( \dfrac{1}{n+1} \dbinom{2n}{n} \)

They can be calculated readily enough:

• in WolframAlpha using catalannumber[n]
• in SageMath using catalan_number(n). 

Talking of SageMath, I've installed the latest version (8.1) on my Mac and am making a concerted effort to make more use of it. I first made a blog post about this free, open source software program in 2017 on the 4th of January. It really is quite impressive in its capabilities so hopefully I can become more adept at using it. Here's a screenshot from my SageMath notebook:

Lastly, the mathematician who lent his name to these numbers, Eugène Catalan, shouldn't be ignored. He was born on the 30th of May 1814 in Bruges, French Empire (now Belgium) and died on the 14th February 1894 in Liège, Belgium. A biography can be found at MacTutor History of Mathematics archive along with biographies of a great many other mathematicians and other interesting material. I first came across this archive in the early naughties and was fascinated to read about the lives of famous mathematicians who had lent their names to so many mathematical tools that I'd used in previous years. L'Hôpital's Rule was a case in point. Although widely used and a greatly useful mathematical tool, who knows anything about the impressively named Guillaume François Antoine Marquis de L'Hôpital who lent his name to the rule?

on Sunday, March 28th 2021

layout improved

Catalan Numbers

Today I turned \(24285\) days old and Figure 1 shows my Twitter post to commemorate the occasion:

Figure 1

The sequence referred to in the tweet is OEIS A178854 and its members, up to and including \(384733\), can be generated using the SageMath code shown in Figure 2.

Figure 2: permalink

The resultant output is: 1, 1, 5, 13, 29, 29, 93, 221, 221, 733, 1757, 3805, 7901, 7901, 24285, 57053, 122589, 122589, 384733, 384733.

Of course, it got me thinking about what a Catalan number is (let alone an odd Catalan number). It turns out that "the only Catalan numbers \(C_n\) that are odd are those for which \(n = 2^k − 1\). All others are even" (Wikipedia). But firstly, what are the Catalan numbers? Here is a definition from the same Wikipedia source where zero-based numbering is used and the \(n\)-th Catalan number is given by:$$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\text{for }n\ge 0$$The first Catalan numbers for n = 0, 1, 2, 3, ... are:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ... (sequence A000108 in the OEIS)

Note that when \(n =2^2-1=3, n = 2^3-1=7, n=2^4-1=15\) etc., the corresponding Catalan numbers are odd (\(5, 429, 9694845\)). The odd Catalan numbers form the OEIS A038003. Of interest here of course is the 15th Catalan number \(9694845\) and the fact that \(9694845 \! \! \mod 2^{15}= 24285\). 

An example of the practical applications of Catalan numbers is shown in Figure 3 (again taken from the Wikipedia article) illustrating their application to Dyck paths:

Figure 3

Of course there's a lot more to Catalan numbers than this and reading the Wikipedia article thoroughly as well the WolframAlpha entry is a start to understanding these numbers more deeply.

on December 19th 2020

There is a later post on April 15th 2018 titled
Sums of Squares of Integers and Catalan Numbers