Motzkin number

Definition

Let $n \ge 0$ be an integer. A Motzkin path of length $n$ is a lattice path $(p_0, p_1, \ldots, p_n)$ in $\Z^2$ with these properties:

$p_0 = (0, 0)$ and $p_n = (n, 0)$ ;
each step $p_i - p_{i-1}$ is one of $U = (1, 1)$ , $D = (1, -1)$ and $H = (1, 0)$ ;
each point $p_i$ has second coordinate at least $0$ .

The Motzkin number $M_n$ is the number of Motzkin paths of length $n$ .

Remarks

Example: the Motzkin paths of length $3$ are $HHH$ , $UDH$ , $HUD$ and $UHD$ , so $M_3 = 4$ . Non-example: the path $HDU$ ends at $(3, 0)$ but fails clause 3, because after two steps it is at height $-1$ .

The first values are $M_0, \ldots, M_7 = 1, 1, 2, 4, 9, 21, 51, 127$ . Splitting a path at its first step gives the recurrence $M_{n+1} = M_n + \sum_{k=0}^{n-1} M_k M_{n-1-k}.$ The generating function $M(z) = \sum_n M_n z^n$ satisfies $M = 1 + z M + z^2 M^2$ , hence $M(z) = \frac{1 - z - \sqrt{1 - 2z - 3z^2}}{2 z^2}.$ Choosing the positions of the $H$ steps gives $M_n = \sum_{k} \binom{n}{2k} C_k$ , where $C_k$ is the Catalan number. The Motzkin paths without $H$ steps are the Dyck words.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Lattice path concept
Motzkin number definition

Tag	`PHA1S6GQGV`
URI	`m2://PHA1S6GQGV`
Kind	definition
Writing	W0 stub
MSC	05A15, 11B83
Defines	Motzkin number
Uses	Lattice path
Changed	2 November 2026

Motzkin number

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here