# Curious Catalan convolutions

Question. Do these identities involving even-index Catalan numbers have a known combinatorial interpretation? They look as though they should. I haven’t seen one in the literature.

$$\sum_{a+b=n}C_{2a}C_{2b}=4^nC_n$$

$$\sum_{a+b=n}C_{2a}{4b\choose 2b}=4^n{2n\choose n}$$

Added. Thanks to Richard Stanley’s helpful answer, I now know that the first of these identities is known in the literature as Shapiro’s Catalan convolution, and has a bijective proof due to Hajnal and Nagy (2014).

Added further. I hadn’t realised quite how straightforwardly each of these identities implies the other. For example, if the first holds then: \begin{align} 2\sum_{a+b=n}C_{2a}{4b\choose 2b}&=2\sum_{a+b=n}(2b+1)C_{2a}C_{2b}\\ &=\Bigl(\sum_{a+b=n}(2a+1)C_{2a}C_{2b}\Bigr)+\Bigl(\sum_{a+b=n}(2b+1)C_{2a}C_{2b}\Bigr)\\ &=(2n+2)\sum_{a+b=n}C_{2a}C_{2b}\\ &=(2n+2)4^nC_n\\ &=2\cdot 4^n {2n\choose n} \end{align} In light of that, a proof of one is essentially also a proof of the other.

Notes. I came across these identities while thinking about an unanswered question of Mike Spivey from 2012. I can define a bijection for the first one – I imagine the second can be done in a similar way – but it isn’t obviously a very nice bijection, and it uses Garsia-Milne involution. Here is a description of it, in the language of species.

If $D$ is the species of Dyck paths with matching up/down pairs labelled (or binary plane trees with internal nodes labelled, etc.) then $D=1+XD^2$, where $1$ is the species of the empty set (sometimes denoted $E_0$) and $X$ is the species of singletons ($E_1$). Split $D=D'+D''$, where $D'$ represents paths of odd semilength and $D''$ even, so we have the mutually recursive isomorphisms \begin{align}\tag{1}D''&=1+2XD'D''\\\tag{2}D'&=X(D'^2 + D''^2)\end{align} (using the $=$ sign to denote isomorphism). The aim is to define an isomorphism between $D''^2$ and $1 + 4X^2D''^4$. We shall do this by defining an isomorphism $$D''^2+Y=1 + 4X^2D''^4+Y$$ for the species $Y=(2XD'D'')^2$, and appealing to the Garsia-Milne principle. Here is the isomorphism, from right to left:

\begin{align} 1 + 4X^2D''^4+Y&=1 + 4X^2D''^2(D'^2+D''^2)\\ &=1 + 4XD'D''^2\tag{using 2}\\ &=1 + 4XD'D''(1+2XD'D'')\tag{using 1}\\ &=1 + 4XD'D'' + 8(XD'D'')^2\\ &=D''^2 + 4(XD'D'')^2\tag{using 1}\\ &=D''^2 + Y \end{align}

• A couple of months ago I had a question essentially in the same vein but for slightly different sequences: if $B$ and $E$ are ogf's for central binomial and trinomial coefficients, find a combinatorial proof for $E(4z)=B(-z)B(3z)$ and $E(2z)E(-2z)=B(z^2)B(9z^2)$. The second identity, of course, follows from the first, but the signed objects are of the other kind. – Alexander Burstein Dec 11 '17 at 5:09
• @AlexanderBurstein Thanks! I hadn’t seen that. In fact the first identity in my question is precisely your $$\left(\frac{C(z)+C(-z)}{2}\right)^2=C(4z^2)$$. – Robin Houston Dec 11 '17 at 13:27