Dyck Words - Revision history

Admin: /* Steep Dyck Words */

2017-07-25T11:58:39Z

Steep Dyck Words

← Older revision		Revision as of 11:58, 25 July 2017
Line 119:		Line 119:
	G_{SW}(1,x,q) = x \sum_{n \geq 0} M_n (q) x^n		G_{SW}(1,x,q) = x \sum_{n \geq 0} M_n (q) x^n
	</math>		</math>

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

			<math>
			D^{\prime} \rightarrow x \overline{x} \| x \overline{x} D^{\prime} \| x D^{\prime} \overline{x} \| x D^{\prime} \overline{x} D^{\prime}
			</math>

			Steep Dyck words cannot be empty and cannot contain any <math>x \overline{x} x</math> sequence.

			This sequence must be generated by the second rule listed,

			<math>
			D^{\prime} \rightarrow x \overline{x} D^{\prime}
			</math>

			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:

			<math>
			S \rightarrow x \overline{x} \| x S \overline{x} \| x S \overline{x} S
			</math>

			Now, letting <math>G_{SW}(x) = \sum_{n \geq 1} S_n x^n</math>, where n denotes steep Dyck words of length 2n, we can deduce

			<math>
			G_{SW}(x) = x + x G_{SW}(x) + x G_{SW}(x)^2
			</math>

			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).

Admin: /* Steep Dyck Words */

2017-07-25T11:51:55Z

Steep Dyck Words

← Older revision		Revision as of 11:51, 25 July 2017
Line 105:		Line 105:

	If <math>(s_{i-1}, s_i)</math> is a southeast step, then <math>(s_{i-2}, s_{i-1})</math> or <math>(s_i, s_{i+1})</math> is also a southeast step		If <math>(s_{i-1}, s_i)</math> is a southeast step, then <math>(s_{i-2}, s_{i-1})</math> or <math>(s_i, s_{i+1})</math> 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 <math>G_{SW}(x,q)</math> 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).

			<math>
			G_{SW}(1,x,q) = x \sum_{n \geq 0} M_n (q) x^n
			</math>

Admin: /* Steep Dyck Words */

2017-07-25T11:42:02Z

Steep Dyck Words

← Older revision		Revision as of 11:42, 25 July 2017
Line 90:		Line 90:

	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 <math>x x \dots x \overline{x} \overline{x} \dots \overline{x}</math>		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 <math>x x \dots x \overline{x} \overline{x} \dots \overline{x}</math>

			===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===		===Steep Dyck Words===

Admin: /* Notes */

2017-07-25T11:38:14Z

Notes

@@ Line 1: / Line 1: @@
 =Notes=
 Dyck words are a mathematical construct that help to connect permutations of letters to form words with combinatoric objects like [[Polyominoes]].
@@ Line 50: / Line 52: @@
 To translate this into plain English: the set <math>X^{\star} = \{ x, \overline{x} \}^{\star}</math> 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.

Admin: Created page with "=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 alphab..."

2017-07-25T11:28:36Z

Created page with "=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 alphab..."

New page

=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.

<math>X</math> - the alphabet, or set of all possible characters/letters

<math>X^{\star}</math> - 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:

<math>
u = u_1 u_2 \dots u_p \in X^{\star}
</math>

<math>
v = v_1 v_2 \dots v_q \in X^{\star}
</math>

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

<math>
w = uv = u_1 u_2 \dots u_p v_1 v_2 \dots v_q
</math>

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

<math>\epsilon</math> 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:

<math>|w|_{a}</math> - number of occurrences of <math>a \in X</math>

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

<math>
|w| = \sum_{a \in X} |w|_a
</math>

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

Rule 1: We require that for any left factor u of w, <math>|u|_x \geq |u|_{\overline{x}}</math>

Rule 2: <math>|w|_{x} = |w|_{\overline{x}}</math>

To translate this into plain English: the set <math>X^{\star} = \{ x, \overline{x} \}^{\star}</math> 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.