8
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Alexander Burstein Dec 11 '17 at 5:09
  • 1
    $\begingroup$ @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)$$. $\endgroup$ – Robin Houston Dec 11 '17 at 13:27
9
$\begingroup$

For the first identity, see additional problem A33 in my book Catalan Numbers. References are given to bijective proofs by Andrews and Nagy.

$\endgroup$
  • $\begingroup$ Marvellous! Thank you so much. The references: G. E. Andrews. On Shapiro’s Catalan convolution. Adv. in Appl. Math., 46:15–24, 2011. G. V. Nagy. A combinatorial proof of Shapiro’s Catalan convolution. Adv. in Appl. Math., 49:391–396, 2012. Also highly relevant is Péter Hajnal and Gábor V. Nagy. A Bijective Proof of Shapiro's Catalan Convolution. Electronic Journal of Combinatorics, 21(2), 2014. $\endgroup$ – Robin Houston Dec 11 '17 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.