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

# Super Catalan Numbers

In 1874, a French and Belgian mathematician Eugène Catalan introduced the numbers

$S(m,n) \equiv \dfrac{(2m)!(2n)!}{m!n!(m+n)!},$

now better known as super Catalan numbers, and stated that the numbers are integers. The entire text of his note in French, an item in a column called Questions which appeared in Nouvelles Annales de Mathématiques Volume 13, is as follows:

$a, b$ étant deux nombres entiers quelconques, la fraction

$\dfrac{(a+1)(a+2)\ldots 2a (b+1)(b+2)\ldots 2b}{1 \cdot 2 \cdot \ldots \cdot (a+b)}$

est égale à un nombre entier.

Unfortunately, there is also another sequence of numbers which goes by the name of super Catalan numbers too, called the Schröder-Hipparchus numbers. It makes the naming a bit ambiguous.

Nevertheless, $S(m,n)$ can be viewed as a generalization of the famous Catalan numbers

\begin{aligned} \mathcal{C}_n = \frac{1}{n+1}\binom{2n}{n},\end{aligned}

because $S(1,n) = 2\mathcal{C}_n.$ You can see the Catalan sequence here in Online Encyclopedia of Integer Sequences (OEIS).

You can prove that $S(m,n)$ is always an integer for any non-negative integers $m$ and $n$ by observing that $S(m,n)$ satisfies

$4S(m,n) = S(m+1,n) + S(m,n+1),$

and that $S(m,0)$ is the central binomial coefficient $\displaystyle\binom{2m}{m} \in \mathbb{Z}$, where we can proceed by induction on $n$. Except for $S(0,0) = 1$, $S(m,n)$ is always even so sometimes $\dfrac{1}{2}S(m,n)$ is considered.

Unlike the Catalan numbers which so far have more than 200 combinatorial interpretations (Richard Stanley gave 66 interpretations in his book Enumerative Combinatorics 2, and he added some more as an addendum), you might be surprised to know that up to date, there is no known combinatorial interpretation of $S(m,n)$. However, there are some combinatorial interpretations of the specific case of super Catalan numbers in terms of pairs of Dyck paths with restricted height (see a paper by Gessel, for instance), cubic plane trees (see a paper by Pippenger and Schleich), or restricted lattice paths (see this paper by Chen and Wang). The first two papers give a combinatorial interpretation for $\dfrac{1}{2}S(m,2)$ and the last one gives a combinatorial interpretation for $S(m,m+s)$ where $0 \le s \le 4$.

There are also weighted interpretations of super Catalan numbers in terms of Krawtchouk polynomials in this paper by Georgiadis, Munemasa, and Tanaka. The most recent work on super Catalan numbers is due to Allen and Gheorghiciuc, who provided a weighted interpretation in terms of positive and negative 2-Motzkin paths in their paper here.

My current research is closely connected to super Catalan numbers, but not in a combinatorial flavor. However, I was curious why people haven’t been able to interpret these seemingly harmless numbers as a counting problem. To do that, I decided to do a bit of detour: I wandered around in the realm of combinatorics. Since one of the interpretations of the Catalan numbers is in terms of Dyck paths, I decided to start with Dyck paths.

To those who are not familiar, a Dyck path $D \in \mathcal{D}_n$ of length $2n$ is a lattice path, starting at $(0,0)$ and ending at $(2n,0)$, that consists of up-steps $(1,1)$ and down-steps $(1,-1)$ and never goes below the $x$-axis. You could also think of Dyck paths of length $2n$ as such paths starting from $(0,0)$ to $(n,n)$ that lies below (but may touch) the diagonal line $y = x$. The number of Dyck paths of length $2n$ is the $n$th Catalan number $\mathcal{C}_n$. You can see some illustrations here.

It thus makes sense to find a combinatorial interpretation of super Catalan numbers in terms of Dyck paths, hoping that the description of $S(m,n)$ relies solely on Dyck paths, only perhaps in more intricate detail. In order to come up with an interpretation, all I need to do is to find a very specific bijection between two Dyck paths that should work in general. That turns out to be a very difficult thing to do. I played with many bijections but none seemed to work. I ended up finding a curious family of bijections between Dyck paths of the same length, though. But more on that later, in another post.

So the moral of the story is you can wish to solve something, but you may end up getting something else. If you are lucky (or unlucky, depends on how you interpret it), that ‘something else’ might just be another question waiting to be discovered 😛