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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_i = (x,y), s_{i+1} = (x+1,y+1)} - Northeast

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s_i=(x,y), s_{i+1} = (x+1,y-1)} - Southeast

Each northwest step Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (s_{i-1},s_i)} corresponds to the letter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle w_i = x}

Each southeast step corresponds to the letter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (s_{i-1}, s_i)} is a southeast step, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (s_{i-2}, s_{i-1})} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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).

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 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).