Dyck Words

Notes

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.