# 2019

To those who are reading this now, I hope you have a happy new year! Now that it’s already 2020, it is time to reflect on what a year 2019 has been for me.

I met new people in 2019, some of whom I become fairly close with. I opened up to more people and was rewarded with some interesting point of view I’ve never known of. My research became more interesting; I have even reached a point where I dreamed about it, although my dreams haven’t given me some inspiration to tackle a proof I am struggling with lol. I travelled to some new places. I stepped out of my comfort zone a lot in 2019.

Overall, 2019 was a good year!

It wasn’t all sunshine and rainbows, though. My relationship didn’t work out. Sometimes I found it hard to sleep because I felt unloved and unwanted. My grandma passed away, from which I still feel a sense of regret at times. Every single time I tackled a problem in my current paper so that it could get submitted immediately, I found another one; to the point where I almost gave up (well, that’s research for you).

Without any intention to complain, I would like to focus this post more on the bitter pills. It’s these life lessons and realisations that hopefully resonate well with you guys and have made me a better person.

Expect less. People keep saying this but I think I fully understand it now. 2019 was the year when I was hurt by my own expectations the most. The problem with me is that I live in the future. I overthink a lot and assume people will return the same amount of energy and affection I pour into them. This creates a conflict within myself. I feel like I am being selfish by insisting that they return the same amount favour I am giving. At the same time, telling myself not to expect anything in return has become harder than usual. It’s like ‘I want to be selfish just this once’. Still, selfishness is selfishness. Nothing can justify it. The solution has been there all along: don’t assume that all people are the same as you. They have their own way to show their affection. I wish I can keep this in my mind all the time.

Don’t expect people to love you if you are not content with yourself. The desire to be loved and accepted is one of the most fundamental feelings we all share, but I learned the hard way that it is not others’ job to love me; it is mine. It is their choice to love and care for me, something we cannot impose. You will attract people who will truly accept you if you accept yourself in the first place. I now think that people who have accepted themselves emanate a more positive aura. One simple thing I am currently working on is to be more opinionated, just not in the bad way. I tend not to show my preference, keeping everything neutral because I am afraid to lose friends. I learned that people who are not afraid to show their preference are more attractive. Articulating your opinion does not necessarily cost you some friends; it lets people know who you are.

Being lonely in the sea of people is the worst feeling. I don’t know if this is because of my age or what, but lately I feel a strong urge to be in a meaningful relationship, be it a friendship or a romantic relationship. I was just doing fine with my alone-ness so this is a very alien feeling for me. Sure, I was in a relationship before, but one of the main reasons why it didn’t work out was because I enjoyed my time with myself more (I worked a lot and we had a long distance relationship). That sudden need, together with my ‘failed attempts’ to garner some, has made me anxious and feeling lonely. Some nights I couldn’t sleep because I couldn’t stop overthinking all the what-ifs you could possibly think of. That feeling, so far, is the worst; even worse than what I felt when I lost my dad some years ago.

Overall, I am at this age where I just feel adulting has never been this hard. I feel like I am not ready to fight all these battles but I have no option that to keep going. But to come think of it again, aren’t we all never ready? I’ll just do my best 🙂

Looking forward to what 2020 has in store for me. May this year be a good year for all of us!

Sydney, 4 January 2020

# Dreams

Cling hard to dreams,
for if it slips away,
you will find yourself

Hold onto dreams,
for if it flies away,
life will be plain
and unalluring.

Dream higher than the moon,
for if you fall,
you will still be
flying among the clouds.

for if you fail,
you can still be

Sydney, 13 October 2019

# Aloofness

Here is a personal thought.

The older I get, I realised that I am getting more capable to care less of what people think of me, except from those I care about. It is becoming easier for me to disregard ignorant or harsh comments from people outside that circle. This sounds like a good change, but I was not entirely happy with the journey. It took me a while to realise that my definition of ‘care less’ was wrong.

I was a sensitive guy. My reliance towards my feeling was strong, despite my academic background which is heavily dependent on logic and rigour, to which I am still quite baffled. I took pride in my ability to empathise with a great number of people, which I didn’t find common amongst my circle of friends. It made me feel good about myself: this ability was one of the reasons I felt unique and I strived to be empathetic every single time. However, it wasn’t all sunshine and rainbows. Sometimes I ended up getting used by my friends, although I would like to think it was unintentional, to solve their problems. In the case where I genuinely wanted to help solve theirs, it would frustrate me when I couldn’t do anything about it.

I am slowly directing myself towards the other direction, to which I have a mixed-up feeling. On one hand, I feel more at peace with myself. I can focus more to my own problems instead of spending more time and energy solving others’. I am also becoming more appreciative towards the power of listening: to simply be there for someone and listen. On the other hand, there is always this constant uneasiness that I have become more aloof, that I have deviated from whom I aspired to be. This is the reason why I wasn’t happy with the change. Something is not quite right but I had no idea what caused it.

My initial guess was that I am disappointed a lot of times by people. Every time it happens, I couldn’t help but blame myself from having an expectation in the first place. It is quite a dilemma for me: not expecting at all is utterly impossible, but expecting something would most likely end up with me getting hurt. My most natural response was to be less empathetic towards people. I shielded myself from any future unnecessary disappointment by being less caring. If I will end up being disappointed anyway, why bother putting an effort to care for someone in the first place? For the first time in my life, I no longer aspired to be an empathetic person.

Obviously there is something wrong with that train of thought. The fact that I know it’s wrong but I couldn’t exactly pinpoint where the problem is frustrates me. It took me a while to arrive at this conclusion: I have been victimising myself while in fact it is my motivation that is corrupt. I feel I deserve to be treated the same way I have given my love and demonstrated my affection towards someone. I ask them to return the favour. I am not as selfless as I thought and it saddens me. Something that I have always thought as unique turns out to be crooked.

It is the subtlety of my corrupt motivation that I figured worth sharing. When you do good to others, it might be totally possible to subconsciously expect something good be done to you in return. I am of the opinion that no matter how hard we try not to do it, we are not going to be truly free from it. We’re humans after all. I am now just trying not to motivate myself to be selfless. The selfish nature of ours will always be existent. All we can do is to minimise its occurrences.

Ideally, caring less of what people think of you should be driven by the awareness that we cannot and must not please all people. We can still be empathetic and having the aforementioned awareness at the same time. Compassion should be always on the table for as long as we live. We don’t have to be aloof to care less.

To value the importance of being empathetic towards people, I was put in a situation where I gave it up, until I realised that it does matter. Life is funny that way.

Sydney, 6 October 2019.

# Matrix Cayley Transform

Sometime ago, in my research, I came across a matrix map I am interested at. It is a generalisation of the complex map

$z \mapsto \dfrac{z-i}{z+i}$

defined on a complex projective plane $\mathbb{C}\mathrm{P}^2$.

Let $\mathbf{F}$ be a field. Given a skew-symmetric matrix $X \in M_n\left(\mathbf{F}\right)$, i.e. $X^T = -X$, one can define the Cayley transform of $X$, denoted by $C(X)$, as

$C(X) = (I-X)(I+X)^{-1},$

for all $X$ such that $I+X$ is invertible.

If we were somewhat more restrictive in our assumption about $\mathbf{F}$, which in this case is to consider an ordered field, then $I+X$ is always invertible for all skew-symmetric matrix $X \in M_n(\mathbf{F})$. To see this, suppose it is not, then there exists a non-zero $\mathbf{u} \in \mathbf{F}^n$ such that $(I+X)\mathbf{u} = \mathbf{0}$, i.e. $X\mathbf{u} = -\mathbf{u}$. However,

$\mathbf{u}^T\mathbf{u} = \left(-X\mathbf{u}\right)^T\mathbf{u} = -\mathbf{u}^TX^T\mathbf{u} = \mathbf{u}^TX\mathbf{u} = -\mathbf{u}^T\mathbf{u},$

which implies $\mathbf{u}^T\mathbf{u} = 0$. Since we are working in an ordered field, this forces $\mathbf{u} = \mathbf{0}$, a contradiction.

It can be shown that $C(X)$ is an orthogonal matrix, i.e. $C(X)^TC(X) = I$ where $I$ is the identity matrix of the same size. It’s not hard to see this by direct computation:

\begin{aligned} C(X)^TC(X) &= \left(\left(I+X\right)^T\right)^{-1}\left(I-X\right)^T(I-X)(I+X)^{-1} \\ &= \left(I-X\right)^{-1}(I+X)(I-X)\left(I+X\right)^{-1} \\ &= \left(I-X\right)^{-1}(I-X)(I+X)\left(I+X\right)^{-1} \\ &= I. \end{aligned}

In the proof above, we used the fact that $I-X$ commutes with $I+X$. Moreover, $\det C(X) = 1$ because

$\det(I-X) = \det\left(I+X\right)^T = \det\left(I+X\right).$

Proposition. The map $C$ is an involution, i.e. $C^2 = \mathrm{id}.$

Example. If $n = 2$, then

$X = \begin{pmatrix} 0 & a \\ -a & 0 \end{pmatrix}$

and

$C(X) = \dfrac{1}{1+a^2}\begin{pmatrix} 1-a^2 & 2a \\ -2a & 1-a^2 \end{pmatrix},$

for some $a \in \mathbf{F}$ satisfying $a^2 + 1 \neq 0$. If $n = 3$, then

$X = \begin{pmatrix} 0 & a & b \\ -a & 0 & c \\ -b & -c & 0 \end{pmatrix}$

so

$C(X) = \dfrac{1}{1+a^2+b^2+c^2}\begin{pmatrix} 1-a^2+b^2+c^2 & 2(-a+bc) & 2(c+ab) \\ 2(a+bc) & 1+a^2-b^2+c^2 & 2(-b+ac) \\ 2(-c+ab) & 2(b+ac) & 1+a^2+b^2-c^2\end{pmatrix},$

for all $a,b,c\in\mathbf{F}$ such that $a^2+b^2+c^2+1\neq 0$.

In Lie group and Lie algebra notation,

$C \enspace \colon \enspace \mathfrak{o}(n) \longrightarrow \mathrm{SO}(n) \le \mathrm{O}(n),$

where $\mathfrak{o}(n)$ is the Lie algebra of skew-symmetric matrices equipped with the usual Lie bracket, $\mathrm{O}(n)$ the Lie group of orthogonal matrices, and $\mathrm{SO}(n)$ a subgroup of $\mathrm{O}(n)$ consisting of orthogonal matrices with determinant 1. We can then think of Cayley transformation as a map from $\mathfrak{o}(n)$ into its Lie group $\mathrm{O}(n)$.

This map is nice because it allows us parametrise rotation matrices! Generally, if one wishes to study a Lie group, one might do that by studying its Lie algebra which behaves much nicer because we can do linear algebra stuff there.

One thing I want to mention about $C$ is that it does not require infinite processes. The formula is precise and does not require approximation. Compare this with the more commonly studied exponential map $\exp$, which is also a map from a Lie algebra $\mathfrak{g}$ to its Lie group $G$:

$\exp(X) = \displaystyle\sum_{k\ge 0} \dfrac{X^k}{k!}$

for $X \in \mathfrak{g}$. In this setting, usually the underlying field is taken to be $\mathbf{R}$ so if one is given $X \in \mathfrak{g}$, one needs to take a limit (which requires infinite processes) to exactly compute $\exp(X)$. It shares a similar property with the Cayley transformation: if $X$ is skew-symmetric, then $\exp(X)$ is orthogonal. In some ways, exponential map is stronger because we have things like

$\exp(aX)\exp(bX) = \exp\left((a+b)X\right),$

for example, while we don’t have an analogue for this with the Cayley transformation. What I mean by that is it’s not possible to find $t \in \mathrm{F}$ as a function of $r,s\in\mathrm{F}$ that satisfies

$C(rX)C(sX) = C(tX)$

for all $X \in \mathfrak{o}(n)$. Nevertheless, it does not mean that the Cayley transformation is less interesting. I feel that this map needs to be more well-studied, especially because it might provide an alternate theory of connecting Lie algebras with Lie groups more algebraically.

I will discuss a generalisation of this Cayley transform to a more general geometric setting in my next post. Roughly speaking (I will make this more rigorous in the next post), given a symmetric, non-degenerate matrix $B$, we can define a symmetric bilinear form $\left(\mathbf{x},\mathbf{y}\right) = \mathbf{x}^TB\mathbf{y}$ for all $\mathbf{x}, \mathbf{y} \in \mathbf{F}^n$. This gives a new geometry, with the case $B = I$ giving the Euclidean geometry back. The matrix $B = \mathrm{diag}(1,1,\ldots,1,-1)$ gives relativistic geometry.

This generalised Cayley transform depends on $B$. We will also see that a modification of being skew-symmetric and orthogonal with respect to $B$ in the next post.

Brisbane, 28 June 2019.

# My first book

On one rainy morning in November,
just a few days shy of your birthday,
you came to see me.

We have only known each other for several months,
but it seemed like we have been friends
for the longest time.

a book that was partially soaking wet,
and then placed it in my hand.

You told me to read it.
I laughed.
You knew I couldn’t read well.

I gave it back to you.

I couldn’t remember what you said to persuade me,
it was million years ago,
but you won. I promised you to read it.

You smiled ever so beautifully,
my attempt not to smile back failed miserably.
You told me you’d come back to make sure I read it.

You never did.

I never opened the book.
I buried it deep inside my closet,
because the sight of it reminded me of you.

But I made you a promise.
It takes exactly two years, three months, and seventeen days
to finally let you go.

Today, I want you to know,
although I believe you were watching me the whole time
from up there,

that I have finally finished reading my first book.

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

# 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 $n$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 $\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.

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

Below we see the Dyck paths of semilength 4:

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.

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.