Motzkin number

Motzkin number
Named after	Theodore Motzkin
Publication year	1948
Author of publication	Theodore Motzkin
No. of known terms	infinity
Formula	see Properties
First terms	1, 1, 2, 4, 9, 21, 51
OEIS index	A001006 ; Motzkin;

Last updated December 13, 2024

In mathematics, the $n$ th Motzkin number is the number of different ways of drawing non-intersecting chords between $n$ points on a circle (not necessarily touching every point by a chord). The Motzkin numbers are named after Theodore Motzkin and have diverse applications in geometry, combinatorics and number theory.

Examples

The following figure shows the 9 ways to draw non-intersecting chords between 4 points on a circle ( $M 4 = 9$ ):

The following figure shows the 21 ways to draw non-intersecting chords between 5 points on a circle ( $M 5 = 21$ ):

Properties

The Motzkin numbers satisfy the recurrence relations

M_{n}=M_{n-1}+\sum _{i=0}^{n-2}M_{i}M_{n-2-i}={\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},

and inversely,^[1]

C_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}M_{k}

This gives

\sum _{k=0}^{n}C_{k}=1+\sum _{k=1}^{n}{\binom {n}{k}}M_{k-1}.

The generating function $m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}$ of the Motzkin numbers satisfies

x^{2}m(x)^{2}+(x-1)m(x)+1=0

and is explicitly expressed as

m(x)={\frac {1-x-{\sqrt {1-2x-3x^{2}}}}{2x^{2}}}.

An integral representation of Motzkin numbers is given by

M_{n}={\frac {2}{\pi }}\int _{0}^{\pi }\sin(x)^{2}(2\cos(x)+1)^{n}dx

.

They have the asymptotic behaviour

M_{n}\sim {\frac {1}{2{\sqrt {\pi }}}}\left({\frac {3}{n}}\right)^{3/2}3^{n},~n\to \infty

.

A Motzkin prime is a Motzkin number that is prime. Four such primes are known:

2, 127, 15511, 953467954114363 (sequence A092832 in the OEIS )

Combinatorial interpretations

The Motzkin number for $n$ is also the number of positive integer sequences of length $n - 1$ in which the opening and ending elements are either 1 or 2, and the difference between any two consecutive elements is −1, 0 or 1. Equivalently, the Motzkin number for $n$ is the number of positive integer sequences of length $n + 1$ in which the opening and ending elements are 1, and the difference between any two consecutive elements is −1, 0 or 1.

Also, the Motzkin number for $n$ gives the number of routes on the upper right quadrant of a grid from coordinate (0, 0) to coordinate ( $n$ , 0) in $n$ steps if one is allowed to move only to the right (up, down or straight) at each step but forbidden from dipping below the $y$ = 0 axis.

For example, the following figure shows the 9 valid Motzkin paths from (0, 0) to (4, 0):

There are at least fourteen different manifestations of Motzkin numbers in different branches of mathematics, as enumerated by Donaghey & Shapiro (1977) in their survey of Motzkin numbers. Guibert, Pergola & Pinzani (2001) showed that vexillary involutions are enumerated by Motzkin numbers.

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In mathematics, the Bernoulli numbers $B n$ are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in the Taylor series expansions of the tangent and hyperbolic tangent functions, in Faulhaber's formula for the sum of m-th powers of the first n positive integers, in the Euler–Maclaurin formula, and in expressions for certain values of the Riemann zeta function.

In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. So, two combinations are identical if and only if each combination has the same members. If the set has n elements, the number of k-combinations, denoted by $or, is equal to the binomial coefficient$

In mathematics, the Euler numbers are a sequence E_n of integers defined by the Taylor series expansion

In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730). They were rediscovered and given a combinatorial meaning by Masanobu Saka in 1782.

In number theory and combinatorics, a partition of a non-negative integer $n$ , also called an integer partition, is a way of writing $n$ as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, $4$ can be partitioned in five distinct ways:

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form, by some expression involving operations on the formal series.

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

<span class="mw-page-title-main">Harmonic number</span> Sum of the first n whole number reciprocals; 1/1 + 1/2 + 1/3 + ... + 1/n

In mathematics, the $n$ -th harmonic number is the sum of the reciprocals of the first $n$ natural numbers:

The Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after Eugène Catalan, though they were previously discovered in the 1730s by Minggatu.

In geometry, a diagonal is a line segment joining two vertices of a polygon or polyhedron, when those vertices are not on the same edge. Informally, any sloping line is called diagonal. The word diagonal derives from the ancient Greek διαγώνιος diagonios, "from corner to corner" ; it was used by both Strabo and Euclid to refer to a line connecting two vertices of a rhombus or cuboid, and later adopted into Latin as diagonus.

In mathematics, the double factorial of a number $n$ , denoted by $n ‼$ , is the product of all the positive integers up to $n$ that have the same parity as $n$ . That is,

In mathematics, Apéry's theorem is a result in number theory that states the Apéry's constant ζ(3) is irrational. That is, the number

In mathematics the nth central binomial coefficient is the particular binomial coefficient

In mathematics, particularly in combinatorics, a Stirling number of the second kind is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by $or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling.$

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the unsigned Stirling numbers of the first kind count permutations according to their number of cycles.

In mathematics, a Delannoy number $counts the paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (m, n), using only single steps north, northeast, or east. The Delannoy numbers are named after French army officer and amateur mathematician Henri Delannoy.$

In mathematics, the Schröder number $also called a large Schröder number or big Schröder number, describes the number of lattice paths from the southwest corner of an grid to the northeast corner using only single steps north, northeast, or east, that do not rise above the SW-NE diagonal.$

In mathematics, the telephone numbers or the involution numbers form a sequence of integers that count the ways $n$ people can be connected by person-to-person telephone calls. These numbers also describe the number of matchings of a complete graph on $n$ vertices, the number of permutations on $n$ elements that are involutions, the sum of absolute values of coefficients of the Hermite polynomials, the number of standard Young tableaux with $n$ cells, and the sum of the degrees of the irreducible representations of the symmetric group. Involution numbers were first studied in 1800 by Heinrich August Rothe, who gave a recurrence equation by which they may be calculated, giving the values

In mathematics, a transformation of a sequence's generating function provides a method of converting the generating function for one sequence into a generating function enumerating another. These transformations typically involve integral formulas applied to a sequence generating function or weighted sums over the higher-order derivatives of these functions.

References

↑ Yi Wang and Zhi-Hai Zhang (2015). "Combinatorics of Generalized Motzkin Numbers" (PDF). Journal of Integer Sequences (18).

Bernhart, Frank R. (1999), "Catalan, Motzkin, and Riordan numbers", Discrete Mathematics , 204 (1–3): 73–112, doi: 10.1016/S0012-365X(99)00054-0
Donaghey, R.; Shapiro, L. W. (1977), "Motzkin numbers", Journal of Combinatorial Theory , Series A, 23 (3): 291–301, doi: 10.1016/0097-3165(77)90020-6 , MR 0505544
Guibert, O.; Pergola, E.; Pinzani, R. (2001), "Vexillary involutions are enumerated by Motzkin numbers", Annals of Combinatorics , 5 (2): 153–174, doi:10.1007/PL00001297, ISSN 0218-0006, MR 1904383, S2CID 123053532
Motzkin, T. S. (1948), "Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products", Bulletin of the American Mathematical Society , 54 (4): 352–360, doi: 10.1090/S0002-9904-1948-09002-4

External links

Weisstein, Eric W. "Motzkin Number". MathWorld .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Yi Wang and Zhi-Hai Zhang (2015). "Combinatorics of Generalized Motzkin Numbers" (PDF). Journal of Integer Sequences (18).

[1]