Skip to main content
2 of 5
Update in response to useful information from Stanley’s answer
Robin Houston
  • 2.9k
  • 1
  • 30
  • 49

Curious Catalan convolutions

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). Is anything known of the other?

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 (nor have I even seen these identities), but the combinatorics literature is large and I am small.

$$\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}$$


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}$$

Robin Houston
  • 2.9k
  • 1
  • 30
  • 49