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 of length (or of semilength ) is a lattice path which starts at and ends at which does not cross above the diagonal line (but if it touches the line, it’s okay).
Another interpretation for , one which I will use throughout this series of posts, is as a path from that ends at which consists of a series of up-steps and down-steps such that it never goes below the -axis.
Let be the set of all Dyck paths of length . It is well-known that
the th 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 the set of all Dyck words of length . 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 and .
Below is an example of a Dyck path in . We can encode this Dyck path into uuduuddd.
There are only Dyck paths of semilength 2, which are
Below we see the Dyck paths of semilength 4:
which, as you can see, are in total.
Note that if a Dyck word is given, for any , in the first subword, the number of u must not exceed the number of d, for otherwise the Dyck path will cross below the -axis. It is also obvious that the number of u and d in any Dyck word of length must both be equal to .
Dyck path tunneling
Given a Dyck path , define a tunnel in to be the horizontal segment between two lattice points of that intersects only in these two points and stays always below . If , then has exactly tunnels and each tunnel can be associated with a pair of (u,d) such that the u step and the d step are connected by a tunnel. In the Dyck path in Figure 1 above, we have 4 tunnels: those connecting with , with , with , and with . See all the tunnels in red dashed line below.
Given a Dyck path , a step is called the conjugate of step if there is a tunnel connecting step and step of . If step is the conjugate of step , we write . Note that the conjugation map is an involution, i.e. for all . In the Dyck path above, for example, , , , and .
Associating to a Dyck path a permutation
Let be the set of permutation of elements in the set . Given a Dyck path , we can associate to it a permutation via the following rules:
- Read the Dyck word of from left to right.
- If the k-th u from this Dyck word falls in position , then define , where .
- If the k-th d from this Dyck word falls in position , then define , where .
This association gives an injective map from to . To give an illustration, the Dyck path in Figure 1 above corresponds to
Now observe that for any Dyck path that is associated with , it is necessary that (resp. ) 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 be given. We can associate to it a string of length consisting of letters , each appearing exactly twice, via the following rules:
- Pair the steps and so that they are connected by a tunnel.
- Label the -th and -th position of this string with one out of letters .
- 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 , but it can also correspond to . 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.