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 nth 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 😛

The Art of Doing Research

I write this post especially to share my experience in doing research. Now that I have graduated from ITB already, I continue my past thesis project as undergraduate student to a whole new level. I worked in a much more general situation than previous research project and it is kind of abstract, especially to those who are not familiar with my field, harmonic analysis.

So, basically my past thesis project is about strong and weak classical Morrey spaces \mathcal{M}^p_q(\mathbb{R}^n), the set of all measurable function f where \|f\|_{\mathcal{M}^p_q} < \infty, where

\|f\|_{\mathcal{M}^p_q} = \sup\limits_{\substack{a \in \mathbb{R}^n \\ r > 0}} |B(a,r)|^{\frac{1}{p} - \frac{1}{q}} \left(\int_{B(a,r)} |f(x)|^q\ dx\right)^{\frac{1}{q}}.

My main objective was to prove that strong Morrey spaces are contained in its weak spaces w\mathcal{M}^p_q(\mathbb{R}^n), and the inclusion is proper. I studied the structure of the spaces and the behaviour of some nice integral operators defined on it.

To learn something new like that, I spent most of my time reading the papers my supervisor gave me and conducted a little experiment. Do not imagine this experiment conducted in a laboratory. There is no (physical) laboratory at all! My research kit is just a stack of paper and a nice pen. Sometimes I need good food and good music. That’s all. I can just do my research in a restaurant or in a cafe or in my own room or even in the toilet (although that’d be unwise). I spent most of my time imagining, since there is no way I can touch, feel, or see the Morrey spaces. Very cheap yet very abstract.

Turns out, with high effort and lots of luck, I could prove what I was supposed to do. Up until this point, I am still amazed by that miracle.

Now I am working with the generalized version, i.e. generalized Morrey spaces \mathcal{M}^p_{\phi}. You might not want to see the definition. It is rather disgusting lol. But as the name suggests, it is a generalized version of the classical Morrey spaces. With certain \phi, we can have \mathcal{M}^p_{\phi} = \mathcal{M}^p_q. What I want to show now is that two norms in two different Morrey spaces are not equivalent. To prove that, I have to find a certain function that satisfies my hypotheses. I am spending much of my time now just to find a single function.

Now that I have been stuck for at least a month, I learn that

  1. Research needs patience and perseverance. You have to know that you will fail most of the times. At first, it seems frustrating. But hey, successful people must learn how to fail. As long as the number of failure is not infinity, I should be okay.
  2. Not many people will be able to help you. Unlike undergraduate or graduate courses which may be taken by students at the same time, research is way more personal. You should be the one who know the most about your object of study, among with other fellow researchers working in the same field.
  3. Ideas can come at an unexpected time. Sometimes when I just happen to have some ideas or just think of some approach, I immediately jot it down in a piece of paper. I fear that the ideas will never come to me again lol. Some people even say that if you do not dream about it, you haven’t done your research well. Lucky I dreamed about it once.
  4. The feeling of successfully proving something you want to prove is just indescribable. I can smile all day and the day after if that happens. On the contrary, I can be very gloomy if for a month or so, I still couldn’t get the correct approach of solving my problem. Yes, I am referring to what I feel now.
  5. You just cannot stop doing research, once you begin. For someone who is at times can be very curious (to the point where it’s kind of annoying) like me, being able to know more only shows that we actually do not know anything. That is why once you do research, you know what you know and you do not know, and since you do not know that you do not know, you want to know more. That happens all the time.
  6. Good food and good music are good catalysts. Well, since research in pure mathematics only requires paper and pen, of course I have to maintain my mood. That is, by eating a lot of delicious food. And singing. And traveling. And writing like this. This is just my way to regain my mood of doing research. I do hope after writing this and finally going back sleeping, ideas can come to me.

The more I do research, the more I am sure that this is my world. I just love doing research.

Penelitian HIMATIKA ITB: Implementasi Kurikulum Belajar Matematika untuk Siswa Tunanetra di Sekolah Dasar

Halooo. Lama banget gak nulis disini. Lagi sibuk ujian banyak banget. Sekarang mau share sedikit dooong.

Jadi, himpunan saya HIMATIKA ITB sedang mengadakan penelitian jangka panjang nih. Penelitiannya sederhana: kita ingin membuat suatu kurikulum belajar matematika bagi siswa tunanetra, yang kita khususkan hanya untuk siswa SD kelas 1 dulu.

Kenapa bikin penelitian ini, lebih didasari pada keprihatinan kita melihat fenomena yang ada di Indonesia. Masih belum ada perhatian khusus yang dari pemerintah untuk mengakomodasi kebutuhan pendidikan adik-adik kita yang berkebutuhan khusus. Padahal jelas kebutuhannya berbeda dan sistem pengajarannya tidak dapat disamakan. Sekarang ini fenomenanya, belum ada sistem pembelajaran yang baik yang diterapkan ke SLB. Mereka masih mencomot kurikulum secara umum yang dibuat pemerintah. Belum lagi kurikulum yang dibuat pemerintah juga tidak ada jaminan kualitas yang memadai. 

Saya tidak memiliki kapasitas untuk mengatakan seberapa baik atau buruk kurikulum yang ada sekarang. Meskipun pendapat saya pribadi mengatakan kurikulum 2013 tidak dipersiapkan dengan baik dan terkesan sekenanya, postingan kali ini bukan untuk membahas itu.

Kembali ke topik. Jadi, penelitian ini judulnya Voice Recording sebagai Alat Bantu Belajar Matematika bagi Siswa Tunanetra di Sekolah Dasar, seperti yang bisa dilihat di bawah ini.Image

Penelitian ini sih idenya sudah ada sejak tahun lalu, dan dilanjutkan di kepengurusan sekarang untuk dieksekusi. Harapannya, ini bisa jadi penelitian jangka panjang dan bisa merambah ke kelas 2 SD, bahkan sampai kelas 6 SD.

Karena kita himpunan mahasiswa matematika, kita bisa buat kurikulum di pembelajaran matematika. Nah, saya mau ajak teman-teman yang tertarik untuk bantu. Bantuan bisa berupa apa saja, bisa berupa ide, ataupun bantuan fisik. Kebetulan kami juga sudah mendapat bantuan dana untuk mengeksekusi acara ini, sehingga kami ingin bisa mewujudkan kegiatan penelitian ini dengan sebaik-baiknya. Metode penelitian bisa dilihat pada poster di atas. Kalau ada masukan atau kritikan, silakan langsung komen saja. Terima kasih banyak 🙂