For a natural number $n$, let $$C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{n!(n+1)!}$$be the $n$-th Catalan number. Prove that for any natural number $m$, $$\sum_{i+j+k=m} C_{i+j}C_{j+k}C_{k+i}=\frac{3}{2m+3}C_{2m+1}.$$ Proposed by Bin Wang
Problem
Source: 2024 CTST P13
Tags: combinatorics
24.03.2024 06:26
Firstly, we have $$\sum_{i+j+k = m}C_{i+j}C_{j+k}C_{k+i} =\underset{0\leq u,v,w\leq m}{\sum_{u+v+w=2m}}C_uC_vC_w$$And $$\sum_{u+v+w = 2m}C_uC_vC_w = \sum_{w=0}^{2m}C_{2m +1 - w}C_w = C_{2m+2} - C_{2m+1}$$Otherwise, $$\sum_{u+v+w=2m, u\geq m+1}C_{u}C_vC_w = \sum_{u=m+1}^{2m}C_uC_{2m+1-u} =\frac{1}{2}\sum_{u=1}^{2m}C_uC_{2m+1-u} = \frac{1}{2}C_{2m+2}-C_{2m+1}$$Hence, $$\text{LHS} =C_{2m+2} - C_{2m+1} - 3\left(\frac{1}{2}C_{2m+2} - C_{2m+1}\right) = 2C_{2m+1} - \frac{1}{2}C_{2m+2}=\text{RHS}\text{ (Q.E.D)}$$
24.03.2024 06:52
LLL2019 wrote: For a natural number $n$, let $$C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{n!(n+1)!}$$be the $n$-th Catalan number. Prove that for any natural number $m$, $$\sum_{i+j+k=m} C_{i+j}C_{j+k}C_{k+i}=\frac{3}{2m+3}C_{2m+1}.$$ Could you tell me which country's TST is CTST? China, Canada?...
24.03.2024 06:56
anh1110004 wrote: Could you tell me which country's TST is CTST? China, Canada?... China.
26.06.2024 00:27
We will use the fact that $C_n$ counts the number of triangulations of a $n+2$-gon. Consider a triangulation of a $(2m+3)$-gon with a vertex $A$. Notice that there must exist a triangle that contains the center of the polygon and there is a $\frac{3}{2m+3}$ probability that $A$ is a vertex of the triangle. Assume that $A$ is a vertex of this triangle, say $ABC$. Then the number of ways to triangulate arc $AB$, $BC$, and $CA$ as $B$ and $C$ vary is given by the sum on the LHS but it is simply equal to $\frac{3}{2m+3}C_{2m+1}$.
27.09.2024 07:16
Very nice...