[Math] Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle – is there a combinatorial explanation

catalan-numbersco.combinatoricsreference-requestrt.representation-theory

This question arose from an answer to my recent question How many traces are there on Temperley-Lieb, Fuss-Catalan, Iwahori-Hecke, Birman-Wenzl-Murakami-Kauffman, … algebras?

What I need from that answer here is combination of the following facts.

0) Let $V$ be the standard (2-dimensional) representation of the Lie algebra $\mathfrak{sl}_2$ (over complex numbers, say).

1) Dimension of the algebra $\operatorname{End}_{\mathfrak{sl}_2}(V^{\otimes n})$ is $C_n$, the $n$-th Catalan number.

2) Let $V^{\otimes n}=m_{n,0}\mathbf{1}\oplus m_{n,1}V\oplus m_{n,2}S^2(V)\oplus m_{n,3}S^3(V)\oplus\cdots$ be the decomposition into irreducible representations of $\mathfrak{sl}_2$, then the above endomorphism algebra decomposes accordingly into the product of full square matrix algebras $\operatorname{Mat}_{m_{n,0}}\times\operatorname{Mat}_{m_{n,1}}\times\operatorname{Mat}_{m_{n,2}}\times\cdots$.

3) It follows easily from the formula $V\otimes S^k(V)\cong S^{k-1}(V)\oplus S^{k+1}(V)$ used in the above answer that the numbers $m_{n,k}$ form the Catalan triangle

1
0   1
1   0   1
0   2   0   1
2   0   3   0   1
0   5   0   4   0   1
5   0   9   0   5   0   1

That is, $m_{n,k}=m_{n-1,k-1}+m_{n-1,k+1}$ for $k\geqslant0$ (starting from $m_{0,0}=1$ and with $m_{n,k}=0$ for $k<0$ or $k>n$).

It thus follows from the above matrix algebra decomposition that the sum of squares of the numbers in the rows of this triangle are the Catalan numbers.

The latter fact seems to be well known. At least it is mentioned at the OEIS page to which my above link points. At that page there also is the formula $m_{n,k}=\frac{k+1}{n+1}\binom{n+1}{\frac{n-k}2}$ (for $n\equiv k\mod 2$, otherwise it is zero).

My question is whether a combinatorial interpretation of this is known. Specifically, whether there are some combinatorial objects enumerated by $m_{n,k}$ such that $C_n$ equals the number of pairs of such objects with equal $k$'s.

LATER

After much hesitation I decided to accept the answer by Qiaochu Yuan. The reason is purely egotistic – that answer helped me personally better to understand the picture (which I reflected in my own answer).

Best Answer

Yes. $C_n$ counts the number of paths from $(0, 0)$ to $(2n, 0)$ which involve moving by either the vector $(1, 1)$ or $(1, -1)$. Each such path passes through $(n, k)$ for a unique $0 \le k \le n$, and the number of paths passing through $(n, k)$ for a fixed $k$ is the square of the number of paths from $(0, 0)$ to $(n, k)$, which is the corresponding term in the Catalan triangle.

In terms of representation theory this corresponds to the identification

$$\operatorname{End}(V^{\otimes n}) \cong \operatorname{Hom}(1, V^{\otimes 2n})$$

(keeping in mind that $V$ is self-dual). In terms of your arrangement of the Catalan triangle the picture to have in mind looks like

 1
 0   1
 1   0   1
 0   2   0   1
 2   0   3   0   1
 0   5   0   4
 5   0   9
 0  14  
14

Exactly the same proof, but for Pascal's triangle rather than the Catalan triangle, gives

$${2n \choose n} = \sum {n \choose k}^2.$$

In terms of representation theory this corresponds to looking at the tensor powers of the defining $2$-dimensional representation of $SO(2)$ rather than $SU(2)$.

Related Question