Catalan determinants in search of a proof: Part II

Question

This problem involves the Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$.

I can prove the below equality by computing each of the two sides, directly. That means, there is an algebraic proof.

QUESTION. Is there a combinatorial or conceptual reason for this equality? $$\det\left[\binom{i+j+a}{i-j+a}\right]_{i,j=0}^{n-1} =\det\left[\frac{\binom{2n+2i+2j}{n+i+j}}{n+i+j+1}\right]_{i,j=0}^{a-1}.$$

POSTSCRIPT.

Let me add a $q$-analogue. Denote $(q)_n=(1-q)\cdots(1-q^n)$ and $\binom{n}k_q=\frac{(q)_n}{(q)_k(q)_{n-k}}$. Then, $$\det\left[q^{\binom{i-j+a}2}\binom{i+j+a}{i-j+a}_q\right]_{i,j=0}^{n-1} =\det\left[\frac{1-q^{2i+1}}{1-q^{n+j+i+1}}\cdot\binom{2n+2j}{n+j+i}_q\right]_{i,j=0}^{a-1}.$$

Answer 1

Here is a combinatorial proof. As my running example, I'll take $a=2$ and $n=3$, so I want to show $$\det \begin{bmatrix} 1 & 3 & 1 \\ 1 & 6 & 5 \\ 1 & 10 & 15 \\ \end{bmatrix} = \det \begin{bmatrix} 5 & 14 \\ 14 & 42 \end{bmatrix}.$$

Remember the Lindström–Gessel–Viennot lemma -- Let $G$ be a directed acyclic graph with specified green vertices $g_1$, $g_2$, ..., $g_k$ and red vertices $r_1$, $r_2$, ..., $r_k$. Let $c_{ij}$ be the number of paths from $g_i$ to $r_j$. Suppose that every collection of $k$ vertex disjoint paths from the $g$'s to the $r$'s joins $g_i$ to $r_i$. Then the number of such collections of paths is $\det (c_{ij})$.

Here I depict graphs with a marked source (green) and sink (red) such that the number of directed paths is a binomial coefficient or Catalan number respectively. All edges are directed either north-east or south-east.

Superimposing several of these, it is easy to make a graph whose noncrossing paths correspond to each determinant. Note that the number of sources and sinks is the size of the determinant, and the length of the paths gives entries in the binomial coefficient/Catalan number.

In each case, there is only one noncrossing way to pairs sources to sinks, and many edges are forced. The forced edges are drawn thinly in the figure below, leaving smaller graphs (with one fewer source-sink pair, in the left hand case).

We now perform a standard trick, turning noncrossing paths into rhombus tilings. In the next figure, the thick lines show one of the possible collections of noncrossing paths in each case. We then slide each path down one unit (shaded) and cover it with rhombi with vertical sides. The remaining area can be uniquely tiled by rhombi with northeasterly and southeasterly sides.

Thus, each determinant counts the number of rhombus tilings of a certain, roughly pentagonal region. But the regions in question are rotations of each other, so the determinants are the same! In general, the region we get is obtained by taking an equiangular hexagon of sides $(a, n-1, n-1, a, n-1, n-1)$ and cutting off a $(120^{\circ},30^{\circ},30^{\circ})$ triangle to leave a pentagon with one jagged edge. The final figure shows the region to be tiled when $a=3$ and $n=6$:

---

UPDATE Your tiling problem is a special case of the one studied by Ciucu and Krattenthaler -- look at Figure 1.1 and set $a=b$ in their notation. They give a product formula for it and prove it by exactly the sort of Gessel-Viennot machinery in this post. They also state that this problem occurs in a paper whose title looks completely unrelated:

Proctor, Robert A., Odd symplectic groups, Invent. Math. 92, No. 2, 307-332 (1988). ZBL0621.22009.

I have not pursued this citation.