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 $ x x \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} | x D^{\prime} \overline{x} | x D^{\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} | x S \overline{x} | x S \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 + x G_{SW}(x) + x G_{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).