Dyck Paths Multiplication (Part 1)

In this series of posts, I will try to introduce a family of mappings between Dyck paths of the same length. The map itself can be thought of as multiplication of two Dyck paths. In this first part, I will lay out all the ingredients needed in order for us to define properly what it means here to multiply two Dyck paths. In the second part, I will define the multiplication map and give some concrete examples. In the third part, I will give a map to reverse the multiplication map we will see in the second post. This is an attempt to show that the family of mappings is indeed a family of bijections between Dyck paths. In the last part, I will highlight several interesting properties about this multiplication map: I have a proof for some observations, but mostly I will be giving some open questions.

Dyck paths and Dyck words

A Dyck path D of length 2n (or of semilength n) is a lattice path which starts at (0,0) and ends at (n,n) which does not cross above the diagonal line y = x (but if it touches the line, it’s okay).

Another interpretation for D, one which I will use throughout this series of posts, is as a path from (0,0) that ends at (2n,0) which consists of a series of up-steps (1,1) and down-steps (1,-1) such that it never goes below the x-axis.

Let \mathcal{D}_n be the set of all Dyck paths of length 2n. It is well-known that

\begin{aligned}\left|\mathcal{D}_n\right| = C_n = \frac{1}{n+1} \binom{2n}{n} \end{aligned},

the nth Catalan number. This gives a combinatorial interpretation of the Catalan numbers in terms of Dyck paths.

Now, given a Dyck path, we can associate to it its Dyck word, which is just the way we read the path from left to right, consisting of a string of us (for up-steps) and ds (for down-steps). Denote by \mathcal{D}_n^\dagger the set of all Dyck words of length 2n. Throughout this post, the terms Dyck path and Dyck word will be interchangeable, unless distinction is required. In other words, most of the times we will make no distinction between the set \mathcal{D}_n and \mathcal{D}_n^\dagger.

Below is an example of a Dyck path in \mathcal{D}_4. We can encode this Dyck path into uuduuddd.

figures1-1

A Dyck path in \mathcal{D}_4 with Dyck word uuduuddd

There are only C_2 = 2 Dyck paths of semilength 2, which are

figures2-1

Below we see the Dyck paths of semilength 4:

figures3-1
figures4-1
figures5-1

which, as you can see, are C_4 = 14 in total.

Note that if a Dyck word is given, for any k \in \{1,2,\ldots,2n\}, in the first k subword, the number of u must not exceed the number of d, for otherwise the Dyck path will cross below the x-axis. It is also obvious that the number of u and d in any Dyck word of length 2n must both be equal to n.

Dyck path tunneling

Given a Dyck path D \in \mathcal{D}_n, define a tunnel in D to be the horizontal segment between two lattice points of D that intersects D only in these two points and stays always below D. If D \in \mathcal{D}_n, then D has exactly n tunnels and each tunnel can be associated with a pair of (u,d) such that the step and the d step are connected by a tunnel. In the Dyck path in Figure 1 above, we have 4 tunnels: those connecting (0,0) with (8,0), (1,1) with (3,1), (3,1) with (7,1), and (4,2) with (6,2). See all the tunnels in red dashed line below.

figures6-1
Tunnels in a Dyck path

Given a Dyck path D \in \mathcal{D}_n, a step j is called the conjugate of step i if there is a tunnel connecting step i and step j of D. If step j is the conjugate of step i, we write j = i^*. Note that the conjugation map ^* is an involution, i.e. (i^*)^* = i for all 1 \le i \le 2n. In the Dyck path above, for example, 1^* = 8, 2^* = 3, 4^* = 7, and 5^* = 6.

Associating to a Dyck path a permutation

Let S_n be the set of permutation of n elements in the set \{1,2,\ldots,n\}. Given a Dyck path D \in \mathcal{D}_n, we can associate to it a permutation \sigma \in S_{2n} via the following rules:

  1. Read the Dyck word D^\dagger of D from left to right.
  2. If the k-th u from this Dyck word falls in position m, then define \sigma(m) = k, where k = 1, 2, \ldots, n.
  3. If the k-th d from this Dyck word falls in position m, then define \sigma(m) = 2n + 1 - k, where k = 1, 2, \ldots, n.

This association gives an injective map from \mathcal{D}_n to S_{2n}. To give an illustration, the Dyck path in Figure 1 above corresponds to

\sigma = \left(1 \enspace 2 \enspace 8 \enspace 3 \enspace 4 \enspace 7 \enspace 6 \enspace 5 \right).

Now observe that for any Dyck path D that is associated with \sigma \in S_{2n}, it is necessary that \sigma(1) = 1 (resp. \sigma(2n) = n+1) because the first (resp. last) step in any Dyck path is always an up-step (resp. a down-step).

Labeling a Dyck path

Let a Dyck path D \in \mathcal{D}_n be given. We can associate to it a string of length 2n consisting of letters x_1, x_2, \ldots, x_n, each appearing exactly twice, via the following rules:

  1. Pair the steps i and j so that they are connected by a tunnel.
  2. Label the i-th and j-th position of this string with one out of n letters x_1, x_2, \ldots, x_n.
  3. Once a letter has been used, it cannot be used anymore.

It is important to note that the order for choosing the letters to use does not matter. For example, the Dyck path in Figure 1 corresponds to x_1x_2x_2x_3x_4x_4x_3x_1, but it can also correspond to x_3x_4x_4x_2x_1x_1x_2x_3. What does matter is the position of the letters.

Now that we have all the stuff we need to know, I will define the multiplication map in the next post.

One thought on “Dyck Paths Multiplication (Part 1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s