Dyck Paths Multiplication (Part 2)

In the previous post, I introduced the notion of Dyck path and Dyck word. I also introduced the concept of tunneling in a Dyck path. We can associate to a Dyck path a permutation. I also mentioned how you can label a Dyck path (or Dyck word) using a set of letters. In this post, I will define what the multiplication map is and give some examples to illustrate this further.

Multiplication of two Dyck paths

Given two Dyck paths D_1, D_2 \in \mathcal{D}_n, we define the product of D_1 and D_2, denoted by D_1 \times D_2, as follows:

  1. Associate to D_2 a permutation \sigma \in S_{2n}.
  2. Pair the steps in D_1 based on its tunnel.
  3. For k = 1, 2, \ldots, 2n, either
    1. write u in k-th position of the word of D_1 \times D_2 if step \sigma(k)^* of D_1 has not been read before, or
    2. write d in k-th position of the word of D_1 \times D_2 if step \sigma(k)^* of D_1 has been read.
  4. Associate the resulting word to its Dyck path, this will be the path D_1 \times D_2.

It is not obvious that the product of two Dyck paths will still yield another Dyck path. Fortunately, this is the case.

Theorem: If D_1, D_2 \in \mathcal{D}_n, then D_1 \times D_2 \in \mathcal{D}_n.

Proof: The resulting word of D_1 \times D_2 will have precisely n up-steps and n down-steps since there are n tunnels in D_1. Moreover, in the first k position, k \in \{1,2,\ldots,2n\}, the number of u will never be smaller than the number of d since the only way a d in position k is produced is to have the pair of step \sigma(k) of D_1 read. Before it is read, a u must have been written at some position l < k. Hence the resulting word is a Dyck word so the associated lattice path is a Dyck path.

Let’s have a look at a couple of examples.

Example 1. Let n = 3 and D_1, D_2 \in \mathcal{D}_3 be represented by uududd and uduudd, respectively. The Dyck path D_2 is associated to

\sigma = \left(1 \enspace 6\enspace 2 \enspace 3 \enspace 5 \enspace 4\right) \in S_6

so the way we read D_1 is we read the 1st step, followed by 6th, 2nd, 3rd, 5th, and 4th steps. Here are the steps to determine D_1 \times D_2:

  1. First we pair the steps in D_1. Step 1 is paired with step 6. Step 2 is paired with step 3, and step 4 is paired with step 5.
  2. We look at step \sigma(1) = 1 of D_1. Its pair, step 6, has not been read before. Hence, step 1 of D_1 \times D_2 is u.
  3. We look at step \sigma(2) = 6 of D_1. Its pair, step 1, has been read. Hence, step 2 of D_1 \times D_2 is d.
  4. We look at step \sigma(3) = 2 of D_1. Its pair, step 3, has not been read before. Hence, step 3 of D_1 \times D_2 is u.
  5. We look at step \sigma(4) = 3 of D_1. Its pair, step 2, has been read. Hence, step 4 of D_1 \times D_2 is d.
  6. We look at step \sigma(5) = 5 of D_1. Its pair, step 4, has not been read before. Hence, step 5 of D_1 \times D_2 is u.
  7. Last, we look at step \sigma(6) = 4 of D_1. Its pair, step 5, has been read. Hence, step 6 of D_1 \times D_2 is d.
  8. The resulting Dyck word is ududud, which can then be interpreted into the Dyck path of D_1 \times D_2.

In other words,

Example 2. Let n = 4 and D_1, D_2 \in \mathcal{D}_4 be represented by uudduudd and uuududdd, respectively. The Dyck path D_2 is associated to \sigma = \left(1 \enspace 2 \enspace 3 \enspace 8 \enspace 4 \enspace 7 \enspace 6 \enspace 5\right) and the steps of D_1 is paired in this manner: step 1 with step 4, step 2 with step 3, step 5 with step 8, and step 6 with step 7. The first step of D_1 \times D_2 is u. The second step of D_1 \times D_2 is again an u since the pair of step \sigma(2) = 2 in $D_1$, which is step 3, has not been read before. The third step of D_1 \times D_2 is d since the pair of step \sigma(3) = 3, which is step 2, has been read before. Continuing this process, the remaining steps are u, d, u, d, and d. Hence,

If P, Q \in \mathcal{D}_n, we can think of this multiplication operator as a map

\begin{aligned} \mu_Q\enspace \colon \mathcal{D}_n &\longrightarrow \mathcal{D}_n,\\ P &\longmapsto P \times Q. \end{aligned}

We will see below how multiplication works in \mathcal{D}_2, \mathcal{D}_3, and \mathcal{D}_4.

Multiplication in \large\mathcal{D}_2

There are only 2 Dyck paths of semilength 2, which are given below.

Two Dyck paths of semilength 2.

It can be verified that

In other words, \mu_1(1) = 1, \mu_1(2) = 2, \mu_2(1) = 2, and \mu_2(2) = 1. We can summarise the above information in a multiplication table below. The convention for D_1 \times D_2 is D_1 is picked from the column below \times, and D_2 is picked from the row to the right of \times.

Multiplication in \mathcal{D}_2

Multiplication in \large\mathcal{D}_3

There are 5 Dyck paths of semilength 3, which are given below.

Five Dyck paths of semilength 3.

The multiplication table is given below.

Multiplication in \mathcal{D}_3

Multiplication in \large\mathcal{D}_4

There are 14 Dyck paths of semilength 4.

Fourteen Dyck paths of semilength 4.

Here is the multiplication table.

Multiplication in \mathcal{D}_4

Further observations

Have a look at any multiplication table I provided above. If you look at any column, you will find every entry in that column to be different. To say it more precisely, given a Dyck path Q \in \mathcal{D}_n where n = 2, 3, 4, if P_1, P_2 \in \mathcal{D}_n with P_1 \neq P_2, then \mu_Q(P_1) \neq \mu_Q(P_2). In other words, \mu_Q is actually a bijection!

To come to think of it, it is not entirely clear that the multiplication map is well-defined (the proof is not as simple as we would like, as you see above), let alone that it is a bijection! If it is indeed a bijection, given any n, we can generate C_n bijections at the same time!

Conjecture. For any Q \in \mathcal{D}_n, the map \mu_Q is a bijection.

In the next post, I will give an explicit algorithm to tackle the following problem: given Q, R \in \mathcal{D}_n, how do you find P \in \mathcal{D}_n such that P \times Q = R? Note that giving such an algorithm doesn’t necessarily mean that it is a bijection. We need to say more to be entirely sure that it is a bijection.

There are several other nice observations about this multiplication, just by looking at the table above. But I think it deserves to be put as a single post, later 🙂

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