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 😛

Intriguing Product of Cosines

Just recently I came across a question on Quora Indonesia (so it’s in Indonesian, which is obvious) about simplifying this expression:

\begin{aligned}\prod_{a=1}^{2015} \prod_{b=1}^{2015} \left(1 + \exp\left(\frac{2\pi i ab}{2015}\right)\right).\end{aligned}

I already wrote my answer there, in Indonesian. That is not as simple as I would expect, but it definitely is interesting enough to force me to write this post.

I was thinking, what if I replace that 2015 by a general positive integer n? In other words, what can we say about

\begin{aligned} \alpha(n) = \prod_{a=1}^{n} \prod_{b=1}^{n} \left(1 + \exp\left(\frac{2\pi i ab}{n}\right)\right)?\end{aligned}

As in what I wrote as an answer in that Quora post, let’s denote 1 + \exp\left(\dfrac{2\pi i ab}{n}\right) by \Lambda(a,b). Every pair of integers (a,b) \in \{1,2,\ldots,n\}^2 will be associated with a complex number \Lambda(a,b).

First, it is quite trivial if n = 1 or n is even. If n = 1, the above expression just boils down to 2. Now, if n = 2k for some k, then \Lambda(1,k) = 0, so the whole product will just be 0. We shall assume from this point that n is an odd number greater than 1.

Now, if either a or b is n, then \Lambda(a,b) = 2. Since there are 2n-1 pairs of (a,b) where at least one of a or b is n, then we can say that

\begin{aligned} \alpha(n) = 2^{2n-1} \prod_{a=1}^{n-1} \prod_{b=1}^{n-1} \Lambda(a,b).\end{aligned}

It is the last product that we should be interested at. Before anything, we shall make a couple of observations about the symmetry of \Lambda(a,b).

  1. For any a and b, \Lambda(a,b) = \Lambda(n-a,n-b), and
  2. For any a, \Lambda(a,b)\Lambda(a,n-b) = 4\cos^2\left(\dfrac{\pi ab}{n}\right) for any b.

These two observations enable us to write

\begin{aligned} \alpha(n) &= 2^{2n-1} \prod_{a=1}^{\frac{n-1}{2}} \left(\prod_{b=1}^{n-1} \Lambda(a,b)\right)^2 \\ &=  2^{2n-1} \prod_{a=1}^{\frac{n-1}{2}} \left(\prod_{b=1}^{\frac{n-1}{2}} 4\cos^2\left(\frac{\pi ab}{n}\right)\right)^2\\ &= 2^{2n-1} \prod_{a=1}^{\frac{n-1}{2}} \left(\prod_{b=1}^{\frac{n-1}{2}} 2\cos\left(\frac{\pi ab}{n}\right)\right)^4\\ &= 2^{2n-1} \times 2^{(n-1)^2}\prod_{a=1}^{\frac{n-1}{2}} \left(\prod_{b=1}^{\frac{n-1}{2}} \cos\left(\frac{\pi ab}{n}\right)\right)^4 \\ &= 2^{n^2} \prod_{a=1}^{\frac{n-1}{2}} \left(\prod_{b=1}^{\frac{n-1}{2}} \cos\left(\frac{\pi ab}{n}\right)\right)^4. \end{aligned}

By now I hope it is already clear why I wrote ‘product of cosines’ in the title. \alpha(n) is, after all, product of cosines. For simplicity, let us define, for every a where 1 \le a \le \dfrac{n-1}{2},

\begin{aligned}\mathcal{C}(a) = \prod_{b=1}^{\frac{n-1}{2}} \cos\left(\frac{\pi ab}{n}\right). \end{aligned}

Our function \alpha(n) is therefore

\begin{aligned} \alpha(n) = 2^{n^2} \prod_{a=1}^{\frac{n-1}{2}} \mathcal{C}(a)^4. \end{aligned}

Now, an observation can be made if n is prime. Define

\begin{aligned}\mathcal{S}(a) = \prod_{b=1}^{\frac{n-1}{2}} \sin\left(\frac{\pi ab}{n}\right), \end{aligned}

and observe that

\begin{aligned}\mathcal{C}(a)\mathcal{S}(a) &= \prod_{b=1}^{\frac{n-1}{2}} \cos\left(\frac{\pi ab}{n}\right)\sin\left(\frac{\pi ab}{n}\right) \\ &= \prod_{b=1}^{\frac{n-1}{2}} \frac{1}{2}\sin\left(\frac{2\pi ab}{n}\right) \\ &= \frac{1}{2^{\frac{n-1}{2}}} \times  \sin\left(\frac{2\pi a}{n}\right) \times \sin\left(\frac{4\pi a}{n}\right)\times \ldots \times \sin\left(\frac{(n-3)\pi a}{n}\right) \times \sin\left(\frac{(n-1)\pi a}{n}\right) \\ &= \frac{1}{2^{\frac{n-1}{2}}}\times\sin\left(\frac{\pi a}{n}\right)\times\sin\left(\frac{2\pi a}{n}\right)\times\sin\left(\frac{3\pi a}{n}\right)\times\sin\left(\frac{(n-1)\pi a}{2n}\right) \\ &= \frac{1}{2^{\frac{n-1}{2}}}\mathcal{S}(a).\end{aligned}

We then observe that \mathcal{S}(a) \neq 0, since none of \dfrac{\pi ab}{n} will be a multiple of \pi if n is prime and both a and b are less than n. Hence,

\begin{aligned} \mathcal{C}(a) = \frac{1}{2^{\frac{n-1}{2}}}\end{aligned}

for every 1 \le a \le \dfrac{n-1}{2}, and thus for n prime we conclude that

\begin{aligned}\alpha(n) = 2^{n^2} \times \left(\frac{1}{2^{\frac{n-1}{2}\times 4}}\right)^{\frac{n-1}{2}} = \frac{2^{n^2}}{2^{(n-1)^2}} = 2^{2n-1}.\end{aligned}

Well, in fact, this is what I initially thought the answer of that Quora question was going to be after trying some small odd integers n to replace 2015. Until I realised that it is going to be more complicated if n is composite. In this case, there will be 1 \le a,b \le \dfrac{n-1}{2} such that \dfrac{\pi ab}{n} is a multiple of \pi, and thus implying \mathcal{S}(a) = 0. In this case, we cannot use the same argument above to find \mathcal{C}(a): we need to think of another way.

At this stage, I really should try to work on the case of n = p_1^{k_1}p_2^{k_2}\ldots p_m^{k_m} but I think it will be much, much more complicated. So, at least for the time being, I will give you a case where n = pq where p and q are two distinct odd primes.

The result above regarding \mathcal{C}(a) can still be salvaged, though. It does still work for those 1 \le a \le \dfrac{n-1}{2} such that \gcd(a,n) = 1. So we need to know: how many such a are there? We can use the Principle of Inclusion-Exclusion to find out.

So, out of the \dfrac{n-1}{2} first positive integers, there will be \left\lfloor\dfrac{n-1}{2p}\right\rfloor numbers that are divisible by p and \left\lfloor\dfrac{n-1}{2q}\right\rfloor numbers that are divisible by q. There will be no number that is divisible by both p and q in the first \dfrac{n-1}{2} positive integers. Hence, there are

\dfrac{n-1}{2} - \left\lfloor\dfrac{n-1}{2p}\right\rfloor - \left\lfloor\dfrac{n-1}{2q}\right\rfloor

such a that are relatively prime to n = pq, where \mathcal{C}(a) = \dfrac{1}{2^{\frac{n-1}{2}}}.

Now, how about those that share the common factor p or q? Let’s have a look at those integers 1 \le a \le \dfrac{n-1}{2} where \gcd(a,n) = p. We can write a = pu for some integer u. Now, in the expansion of

\begin{aligned} \mathcal{C}(a) = \prod_{b=1}^{\frac{n-1}{2}} \cos\left(\frac{\pi kb}{q}\right),\end{aligned}

there will be exactly \left\lfloor\dfrac{n-1}{2q}\right\rfloor terms that are either 1 or -1, coming from those b that are multiples of q. How do we compute the product of other \dfrac{n-1}{2} - \left\lfloor\dfrac{n-1}{2q}\right\rfloor terms?

Well, there’s a trick that we can use. We need to split the product into smaller products.

\begin{aligned}\mathcal{C}(a) = \pm\prod_{b=1}^{\frac{q-1}{2}}\cos\left(\frac{\pi kb}{q}\right)\times\prod_{b=\frac{q+1}{2}}^{q-1}\cos\left(\frac{\pi kb}{q}\right)\times\prod_{b=q+1}^{\frac{3q-1}{2}}\cos\left(\frac{\pi kb}{q}\right)\times\cdots\times\prod_{b=\frac{n-q}{2}+1}^{\frac{n-1}{2}}\cos\left(\frac{\pi kb}{q}\right).\end{aligned}

The plus and minus sign there is due to the product of \cos(jk\pi) for all 1 \le j \le \left\lfloor\dfrac{n-1}{2q}\right\rfloor. It won’t matter which one is the actual sign anyway, since we are interested in \mathcal{C}(a)^4.

Now, have a look at the first product. Since 1 \le b \le \dfrac{q-1}{2} and k < q, none of the \dfrac{\pi kb}{q} will be an integer multiple of \pi. Therefore, we can apply the argument involving the product \mathcal{C}(a) and \mathcal{S}(a) as above to deduce that the first product must be \dfrac{1}{2^{\frac{q-1}{2}}}.

The rest of the products can be viewed exactly as the first product after you apply a suitable trigonometric identity first. For example, in the second product, you need to use \cos(\pi k - \theta) = (-1)^k \cos\theta.

We can then conclude that the product in every group will be \dfrac{1}{2^{\frac{q-1}{2}}}. Since there are \dfrac{2}{q-1}\left(\dfrac{n-1}{2} - \left\lfloor\dfrac{n-1}{2q}\right\rfloor\right) smaller products altogether, we conclude that for 1 \le a \le \dfrac{n-1}{2} such that \gcd(a,n) = p,

\begin{aligned} \mathcal{C}(a) = \left(\frac{1}{2^{\frac{q-1}{2}}}\right)^{\frac{2}{q-1}\left(\frac{n-1}{2} - \left\lfloor\frac{n-1}{2q}\right\rfloor\right)} = \frac{1}{2^{\frac{n-1}{2} - \left\lfloor\frac{n-1}{2q}\right\rfloor}}. \end{aligned}

Using the same reasoning, for 1 \le a \le \dfrac{n-1}{2} such that \gcd(a,n) = q, we have that

\begin{aligned} \mathcal{C}(a) = \left(\frac{1}{2^{\frac{p-1}{2}}}\right)^{\frac{2}{p-1}\left(\frac{n-1}{2} - \left\lfloor\frac{n-1}{2p}\right\rfloor\right)} = \frac{1}{2^{\frac{n-1}{2} - \left\lfloor\frac{n-1}{2p}\right\rfloor}}. \end{aligned}

We are now ready to compute \alpha(n)! From the first \dfrac{n-1}{2} positive integers, there are exactly \dfrac{n-1}{2} - \left\lfloor\dfrac{n-1}{2p}\right\rfloor - \left\lfloor\dfrac{n-1}{2q}\right\rfloor integers whose \mathcal{C}(a) = \dfrac{1}{2^{\frac{n-1}{2}}}. There are \left\lfloor\dfrac{n-1}{2p}\right\rfloor integers whose \mathcal{C}(a) = \dfrac{1}{2^{\frac{n-1}{2} - \left\lfloor\frac{n-1}{2q}\right\rfloor}}, and finally \left\lfloor\dfrac{n-1}{2q}\right\rfloor integers whose \mathcal{C}(a) = \dfrac{1}{2^{\frac{n-1}{2} - \left\lfloor\frac{n-1}{2p}\right\rfloor}}.

Hence,

\begin{aligned} \alpha(n) &= 2^{n^2}\prod_{a=1}^{\frac{n-1}{2}} \mathcal{C}(a)^4 \\ &= 2^{n^2} \left(\dfrac{1}{2^{4 \times \frac{n-1}{2}}}\right)^{\dfrac{n-1}{2} - \left\lfloor\dfrac{n-1}{2p}\right\rfloor - \left\lfloor\dfrac{n-1}{2q}\right\rfloor} \left(\frac{1}{2^{4 \times \left(\frac{n-1}{2} - \left\lfloor\frac{n-1}{2q}\right\rfloor\right)}}\right)^{\left\lfloor\dfrac{n-1}{2p}\right\rfloor} \left(\frac{1}{2^{4 \times \left(\frac{n-1}{2} - \left\lfloor\frac{n-1}{2p}\right\rfloor\right)}}\right)^{\left\lfloor\dfrac{n-1}{2q}\right\rfloor} \\ &= 2^{2n-1+8\left\lfloor\dfrac{n-1}{2p}\right\rfloor\left\lfloor\dfrac{n-1}{2q}\right\rfloor}.\end{aligned}

You already see how complicated it is just in the case where n is a product of two distinct primes. In the original Quora question, n = 2015 = 5 \times 13 \times 31, so there are more cases to consider: those 1 \le a \le \dfrac{n-1}{2} = 1007 such that \gcd(a,2015) = 1, 5, 13, 31, 65, 155, 403. However, the idea stays the same. In this case, \alpha(2015) = 2^{13725}.

I might soon add the case where n = p^k for some k. Hopefully I will have time and energy to do the general case 😛

By the way, I am quite certain there is a more elegant way to find \alpha(n). You know, \Lambda(a,b) is too simple for the product to be this complicated. But maybe I am wrong…