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

Improve this question
$\endgroup$
2
  • 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
    Commented Dec 11, 2017 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
    Commented Dec 11, 2017 at 13:27

1 Answer 1

Reset to default
12
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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
    Commented Dec 11, 2017 at 1:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .