Catalan numbers as sums of squares of numbers in the rows of the Catalan triangle - is there a combinatorial explanation?

Question

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

Answer 1

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)$.

Answer 2

Another way of looking at it is that $m_{n,n-2i}$ is the number of standard Young tableaux of shape $(n-i,i)$. An elegant proof that $\sum_k m_{n,k}^2=C_n$ goes back to MacMahon. Take a standard Young tableau $T$ of shape $(n,n)$ (of which there are $C_n$), let $A$ be the part occupied by $1,2,\dots,n$, and let $B$ be the part occupied by $n+1,n+2,\dots,2n$, rotated $180^\circ$, with the entry $i$ replaced by $2n+1-i$. See Enumerative Combinatorics, vol. 2, Exercise 6.19(xx) or Catalan Numbers, Chapter 2, item 169.

Answer 3

Being perplexed by the choice - which of the answers to accept - on top of that I've come up with yet another answer, inspired by the one by Qiaochu Yuan.

Consider the $\textit{generic Temperley-Lieb category}$ (my source is "Notes for Mike Freedman" by Goodman and Wenzl, probably there is a more appropriate reference, I just grabbed the first sensible one from Google).

This is a monoidal linear category generated by a self-dual object $V$, so the only objects are $V^{\otimes n}$, $n\geqslant0$. Linearity is over polynomials in an indeterminate $q$, and the composite $\mathbf1\xrightarrow[\textrm{(unit)}]{}V\otimes V\xrightarrow[\textrm{(counit)}]{}\mathbf1$ is $q$ times the identity.

These features more or less determine the category uniquely.

The category is self-dual, $\operatorname{Hom}(V^{\otimes n_1},V^{\otimes n_2})$ and $\operatorname{Hom}(V^{\otimes n_2},V^{\otimes n_1})$ are (canonically) isomorphic. Morphisms $V^{\otimes n_1}\to V^{\otimes n_2}$ are linear combinations of Temperley-Lieb diagrams with $n_1$ inputs and $n_2$ outputs, and each such diagram can be factored uniquely through $V^{\otimes k}$ for some smallest $k$.

Uniqueness implies that the rank of $\operatorname{Hom}(V^{\otimes n_1},V^{\otimes n_2})$ is the sum over $k$ of products of ranks of $\operatorname{Hom}_\twoheadrightarrow(V^{\otimes n_1},V^{\otimes k})$ and of $\operatorname{Hom}_\rightarrowtail(V^{\otimes k},V^{\otimes n_2})$.

Here $\operatorname{Hom}_\twoheadrightarrow\subseteq\operatorname{Hom}$ corresponds to those diagrams with no output points connected with each other, i. e. those morphisms which may be obtained without using the unit $\mathbf1\to V\otimes V$, while $\operatorname{Hom}_\rightarrowtail$ means not connecting input points, resp. not using the counit $V\otimes V\to\mathbf1$.

Purely combinatorially, each Temperley-Lieb diagram factors uniquely through a smallest $k$, so that moreover no points on the $k$ side are connected with each other.

Now the number of such diagrams with $n$ inputs and $k$ outputs (or vice versa) without arcs on the $k$ side is $m_{n,k}$. Indeed, denoting these numbers by $\tilde m_{n,k}$, it is easy to see that they satisfy the same recursion: the number of diagrams with first points of $n$ and $k$ connected is $\tilde m_{n-1,k-1}$ (remove (resp. attach) this connection) while the number of those with first points not connected is $\tilde m_{n-1,k+1}$ (relocate the first point from the $n$ (resp. $k$) side to make it the new first point on the $k$ (resp. $n$) side).

So the rank of both $\operatorname{Hom}_\twoheadrightarrow(V^{\otimes n},V^{\otimes k})$ and $\operatorname{Hom}_\rightarrowtail(V^{\otimes k},V^{\otimes n})$ is the multiplicity number $m_{n,k}$ from the question.

This by the way also gives $$ \sum_km_{n_1,k}m_{n_2,k}=\begin{cases}C_{(n_1+n_2)/2}&,\ n_1\equiv n_2\\0&,\ n_1\not\equiv n_2\end{cases}\mod2. $$

By way of an illustration for factoring morphisms as above -