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

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 $\large\mathcal{D}_3$

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

The multiplication table is given below.

### Multiplication in $\large\mathcal{D}_4$

There are 14 Dyck paths of semilength 4.

Here is the multiplication table.

## 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 🙂