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 , we define the product of and , denoted by , as follows:
- Associate to a permutation .
- Pair the steps in based on its tunnel.
- For , either
- write u in -th position of the word of if step of has not been read before, or
- write d in -th position of the word of if step of has been read.
- Associate the resulting word to its Dyck path, this will be the path .
It is not obvious that the product of two Dyck paths will still yield another Dyck path. Fortunately, this is the case.
Theorem: If , then .
Proof: The resulting word of will have precisely up-steps and down-steps since there are tunnels in . Moreover, in the first position, , the number of u will never be smaller than the number of d since the only way a d in position is produced is to have the pair of step of read. Before it is read, a u must have been written at some position . 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 and be represented by uududd and uduudd, respectively. The Dyck path is associated to
so the way we read is we read the 1st step, followed by 6th, 2nd, 3rd, 5th, and 4th steps. Here are the steps to determine :
- First we pair the steps in . Step 1 is paired with step 6. Step 2 is paired with step 3, and step 4 is paired with step 5.
- We look at step of . Its pair, step 6, has not been read before. Hence, step 1 of is u.
- We look at step of . Its pair, step 1, has been read. Hence, step 2 of is d.
- We look at step of . Its pair, step 3, has not been read before. Hence, step 3 of is u.
- We look at step of . Its pair, step 2, has been read. Hence, step 4 of is d.
- We look at step of . Its pair, step 4, has not been read before. Hence, step 5 of is u.
- Last, we look at step of . Its pair, step 5, has been read. Hence, step 6 of is d.
- The resulting Dyck word is ududud, which can then be interpreted into the Dyck path of .
In other words,
Example 2. Let and be represented by uudduudd and uuududdd, respectively. The Dyck path is associated to and the steps of 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 is u. The second step of is again an u since the pair of step in $D_1$, which is step 3, has not been read before. The third step of is d since the pair of step , which is step 2, has been read before. Continuing this process, the remaining steps are u, d, u, d, and d. Hence,
If , we can think of this multiplication operator as a map
We will see below how multiplication works in , and .
There are only 2 Dyck paths of semilength 2, which are given below.
It can be verified that
In other words, , , , and . We can summarise the above information in a multiplication table below. The convention for is is picked from the column below , and is picked from the row to the right of .
There are 5 Dyck paths of semilength 3, which are given below.
The multiplication table is given below.
There are 14 Dyck paths of semilength 4.
Here is the multiplication table.
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 where , if with , then . In other words, 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 , we can generate bijections at the same time!
Conjecture. For any , the map is a bijection.
In the next post, I will give an explicit algorithm to tackle the following problem: given , how do you find such that ? 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 🙂