Dyck Words

Notes

Dyck Words Definitions

Dyck words are a mathematical construct that help to connect permutations of letters to form words with combinatoric objects like Polyominoes.

Let X be an alphabet. Then we define a free monoid generated by X, which we denote X*, as the set of finite words writen with the letters taken from X.

$X$ - the alphabet, or set of all possible characters/letters

$X^{\star }$ - denotes the monoid generated by X

Now suppose we have two vectors of letters from X, which we will call u and v. These vectors form words.

p will index the word u, q will index the word v.

The product of u and v is the concatenation of these words:

$u=u_{1}u_{2}\dots u_{p}\in X^{\star }$

$v=v_{1}v_{2}\dots v_{q}\in X^{\star }$

The word w is the product, or concatenation, of these letters:

$w=uv=u_{1}u_{2}\dots u_{p}v_{1}v_{2}\dots v_{q}$

The word u is the left factor of the word w.

$\epsilon$ is the empty word/set.

The number of times a letter such as a occurs is denoted as the magnitude of the letter in w, with the letter as a subscript:

$|w|_{a}$ - number of occurrences of $a\in X$

The length of a word is indicated by the sum over all letters of each letter's occurrence:

$|w|=\sum _{a\in X}|w|_{a}$

Now, we can define a set of words w on $X^{\star }=\{x,{\overline {x}}\}^{\star }$ (recall $X^{\star }$ is the set of finite words written with letters from X.

Rule 1: We require that for any left factor u of w, $|u|_{x}\geq |u|_{\overline {x}}$

Rule 2: $|w|_{x}=|w|_{\overline {x}}$

To translate this into plain English: the set $X^{\star }=\{x,{\overline {x}}\}^{\star }$ is basically our choice of whether we are going to take a diagonal upward step, or a diagonal downward step. The first rule ensures that our steps never drop below the x axis.

Now, let us denote a hypothetical Dyck word as

$w=w_{1}w_{2}\dots w_{2n}$

Now we can define an inversion of a pair $w_{i}w_{j}$ as an instance where $w_{i}={\overline {x}},w_{j}=x$ and $i<j$

We can define a "down set" which contains all of these characters:

$D(w)=\{i:w_{i}={\overline {x}}\bigcap w_{i+1}=x,1\leq i\leq n-1\}$

Note that the number of Dyck words of length 2n is equal to the nth Catalan number.

Enumerating words according to inversion number is related to the q-Catalan numbers.

More definitions:

Define a path as a sequence of points in $\mathbb {N} \times \mathbb {N}$

Define a step of a path as a pair of two consecutive points in the path.

Each Dyck word encodes a path $w=(s_{0},s_{1},\dots ,s_{2n})$

Each path has only northeast (upper diagonal) or southeast (lower diagonal) steps. These correspond to steps such that:

$s_{i}=(x,y),s_{i+1}=(x+1,y+1)$ - Northeast

$s_{i}=(x,y),s_{i+1}=(x+1,y-1)$ - Southeast

Each northwest step $(s_{i-1},s_{i})$ corresponds to the letter $w_{i}=x$

Each southeast step corresponds to the letter $w_{i}={\overline {x}}$

The inversion number of a Dyck word w is equivalent to the area of a corresponding Ferrers diagram composed of the difference between the word w and the "default" path of $xx\dots x{\overline {x}}{\overline {x}}\dots {\overline {x}}$

Enumerating Dyck Words

Several extensions of this idea have been made.

• Carlitz q-Catalan numbers count the inversions of Dyck words and Catalan permutations
• q-Catalan numbers (MacMahon, Krattenthaler, Gessel) enumerate Dyck words according to parameters of the down set
• q-Catalan numbers introduced by Polya and Gessel count parallelogram polyominoes according to area

Steep Dyck Words

A Dyck word is steep if the word is non-empty and the word does not contain any xxx factor

These have no "isolated" southeast steps.

If $(s_{i-1},s_{i})$ is a southeast step, then $(s_{i-2},s_{i-1})$ or $(s_{i},s_{i+1})$ is also a southeast step

To count steep parallelogram polyominoes, one may use the Motzkin numbers to count them according to their perimeter.

Classical bijection between parallelogram polyominoes and Dyck words - object grammars provide an explanation.

Can deduce a functional equation satisfied by generating function of steep polyominoes according to width, perimeter, and area.

Let $G_{SW}(x,q)$ denote the steep Dyck word generating function, according to inversino number q and length x.

Via q-grammars, it can be shown that the generating function of steep Dyck words of length 2n, counted by inversion number, is equal to the n-1th q-Motzkin number M(n-1)(q).

$G_{SW}(1,x,q)=x\sum _{n\geq 0}M_{n}(q)x^{n}$

This can be proved by showing the non-empty Dyck words generated by a grammar like

$D^{\prime }\rightarrow x{\overline {x}}|x{\overline {x}}D^{\prime }|xD^{\prime }{\overline {x}}|xD^{\prime }{\overline {x}}D^{\prime }$

Steep Dyck words cannot be empty and cannot contain any $x{\overline {x}}x$ sequence.

This sequence must be generated by the second rule listed,

$D^{\prime }\rightarrow x{\overline {x}}D^{\prime }$

so the steep Dyck words can be generated by the algebraic grammar that consists of all rules except the one that produces invalid Dyck words, namely, the grammar:

$S\rightarrow x{\overline {x}}|xS{\overline {x}}|xS{\overline {x}}S$

Now, letting $G_{SW}(x)=\sum _{n\geq 1}S_{n}x^{n}$, where n denotes steep Dyck words of length 2n, we can deduce

$G_{SW}(x)=x+xG_{SW}(x)+xG_{SW}(x)^{2}$

from which we can find that the Dyck word of length 2n is enumerated by the n-1th Motzkin number

Proving the generating function is given by the q-Motzkin number requires introducing the q-analog of the Dyck word w, called (w;q), which requires the use of q-grammars. (See Schutzemberger or Delest and Fedou).