Maths Olympiad Prep

Library / /6 of 7

Combinatorics Difficulty 8.9 Shortlist Prove it China

Let N={0,1,2,}\mathbb{N} = \{0,1,2,\dots\} be the set of all non-negative integers. For each nNn \in \mathbb{N}, define the Catalan number
Cn=1n+1(2nn)=(2n)!n!(n+1)!. C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{n!(n+1)!}.
Prove that for any positive integer mm, we have
i,j,kNi+j+k=mCi+jCi+kCj+k=32m+3C2m+1. \sum_{\substack{i,j,k \in \mathbb{N} \\ i+j+k=m}} C_{i+j}C_{i+k}C_{j+k} = \frac{3}{2m+3}C_{2m+1}.

Solution

Proof 1. Consider the set of ordered triples:
A={(u,v,w)N3u,v,wm;u+v+w=2m}, A = \{ (u, v, w) \in \mathbb{N}^3 \mid u, v, w \le m; u + v + w = 2m \},
B={(u,v,w)N3u+v+w=2m},B1={(u,v,w)Bum+1}, B = \{(u, v, w) \in \mathbb{N}^3 \mid u + v + w = 2m\}, \quad B_1 = \{(u, v, w) \in B \mid u \ge m + 1\},
B2={(u,v,w)Bvm+1},B3={(u,v,w)Bwm+1}. B_2 = \{(u, v, w) \in B \mid v \ge m + 1\}, \quad B_3 = \{(u, v, w) \in B \mid w \ge m + 1\}.
Then A=B(B1B2B3)A = B \setminus (B_1 \cup B_2 \cup B_3). Therefore,
LHS of (1)=i,j,kNi+j+k=mCi+jCi+kCj+k=(u,v,w)ACuCvCw=(u,v,w)BCuCvCw(u,v,w)B1CuCvCw(u,v,w)B2CuCvCw(u,v,w)B3CuCvCw.(2) \begin{aligned} \text{LHS of (1)} &= \sum_{\substack{i,j,k \in \mathbb{N} \\ i+j+k=m}} C_{i+j}C_{i+k}C_{j+k} = \sum_{(u,v,w) \in A} C_u C_v C_w \\ &= \sum_{(u,v,w) \in B} C_u C_v C_w - \sum_{(u,v,w) \in B_1} C_u C_v C_w - \sum_{(u,v,w) \in B_2} C_u C_v C_w - \sum_{(u,v,w) \in B_3} C_u C_v C_w. \end{aligned} \qquad (2)
By symmetry, the sums over B1B_1, B2B_2, and B3B_3 are the same. Using the recurrence relation for Catalan numbers:
Cn+1=i=0nCiCni=C0Cn+C1Cn1++CnC0, C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i} = C_0 C_n + C_1 C_{n-1} + \dots + C_n C_0,
we have
(u,v,w)BCuCvCw=u=02mCu(v=02muCvC2muv)=u=02mCuC2m+1u=(u=02m+1CuC2m+1u)C2m+1C0=C2m+2C2m+1, \begin{aligned} \sum_{(u,v,w) \in B} C_u C_v C_w &= \sum_{u=0}^{2m} C_u \left( \sum_{v=0}^{2m-u} C_v C_{2m-u-v} \right) = \sum_{u=0}^{2m} C_u C_{2m+1-u} \\ &= \left( \sum_{u=0}^{2m+1} C_u C_{2m+1-u} \right) - C_{2m+1} C_0 = C_{2m+2} - C_{2m+1}, \end{aligned}
(u,v,w)B1CuCvCw=u=m+12mCu(v=02muCvC2muv)=u=m+12mCuC2m+1u=12(u=12mCuC2m+1u)=12(C2m+22C2m+1). \begin{aligned} \sum_{(u,v,w) \in B_1} C_u C_v C_w &= \sum_{u=m+1}^{2m} C_u \left( \sum_{v=0}^{2m-u} C_v C_{2m-u-v} \right) = \sum_{u=m+1}^{2m} C_u C_{2m+1-u} \\ &= \frac{1}{2} \left( \sum_{u=1}^{2m} C_u C_{2m+1-u} \right) = \frac{1}{2} (C_{2m+2} - 2C_{2m+1}). \end{aligned}
Since
C2m+2=(4m+4)!(2m+2)!(2m+3)!=(4m+3)(4m+4)(2m+2)(2m+3)(4m+2)!(2m+1)!(2m+2)!=2(4m+3)2m+3C2m+1, \begin{aligned} C_{2m+2} &= \frac{(4m+4)!}{(2m+2)!(2m+3)!} = \frac{(4m+3)(4m+4)}{(2m+2)(2m+3)} \cdot \frac{(4m+2)!}{(2m+1)!(2m+2)!} \\ &= \frac{2(4m+3)}{2m+3} \cdot C_{2m+1}, \end{aligned}

we have
LHS of (1)=(u,v,w)ACuCvCw=(C2m+2C2m+1)312(C2m+22C2m+1)=2C2m+112C2m+2=32m+3C2m+1=RHS of (1). \begin{align*} \text{LHS of (1)} &= \sum_{(u,v,w) \in A} C_u C_v C_w = (C_{2m+2} - C_{2m+1}) - 3 \cdot \frac{1}{2} (C_{2m+2} - 2C_{2m+1}) \\ &= 2C_{2m+1} - \frac{1}{2}C_{2m+2} = \frac{3}{2m+3}C_{2m+1} = \text{RHS of (1).} \quad \square \end{align*}

Proof 2 (Combinatorial Model). The number of ways to triangulate a convex n-gon P1P2PnP_1P_2\cdots P_n by adding n − 3 non-intersecting diagonals is exactly the Catalan number Cn2C_{n-2}.
This result can be proven by induction on nn. Consider vertex PnP_n. If PnP_n is not connected by any diagonal, then P1P_1 and Pn1P_{n-1} are connected, reducing the problem to the triangulation of a convex n1n-1-gon P1P2Pn1P_1P_2\cdots P_{n-1}, which has Cn3C_{n-3} ways. If PnP_n is connected by a diagonal, let PkP_k (2kn22 \le k \le n-2) be the smallest vertex connected to PnP_n. Then PnP_n and PkP_k are connected, and P1P_1 to Pk1P_{k-1} are not connected to PnP_n. This reduces to triangulating a convex kk-gon P1P2PkP_1P_2\cdots P_k and a convex nk+1n-k+1-gon PkPk+1PnP_kP_{k+1}\cdots P_n, which has Ck2Cnk1C_{k-2}C_{n-k-1} ways. Summing over k=2,,n2k=2, \dots, n-2 and adding Cn3C_{n-3}, we get:
(C0Cn3+C1Cn4++Cn4C1)+Cn3=Cn2. (C_0C_{n-3} + C_1C_{n-4} + \dots + C_{n-4}C_1) + C_{n-3} = C_{n-2}.
Now, consider the original problem. Take the regular 2m+32m+3-gon P1P2P2m+3P_1P_2\cdots P_{2m+3} inscribed in a circle. We triangulate the (2m+3)(2m+3)-gon and select the unique triangle containing the center (the only acute triangle) and designate one vertex. Consider the total number of such operations.
If we first select the designated vertex PuP_u (with 2m+32m+3 choices), then draw the triangle PuPvPwP_uP_vP_w
containing the center, with vu,wvv-u, w-v, and uwu-w modulo 2m+32m+3 belonging to {1,2,,m+1}\{1, 2, \dots, m+1\}, and
the sum of these residues being 2m+32m+3. This corresponds to (i,j,k)N3(i, j, k) \in \mathbb{N}^3 satisfying i+j+k=mi+j+k=m
and
vui+j+1,wvj+k+1,uwk+i+1(mod2m+3). v - u \equiv i + j + 1, \quad w - v \equiv j + k + 1, \quad u - w \equiv k + i + 1 \pmod{2m+3}.
Then, the three regions between the sides of the triangle can be further triangulated, e.g., the
region containing PuPvP_u P_v is a i+j+2i + j + 2-gon, with Ci+jC_{i+j} ways to triangulate.
Thus, the total number of ways is
(2m+3)i,j,kNi+j+k=mCi+jCi+kCj+k. (2m + 3) \cdot \sum_{\substack{i,j,k \in \mathbb{N} \\ i+j+k=m}} C_{i+j} C_{i+k} C_{j+k}.
On the other hand, we can first triangulate the 2m+32m+3-gon, then choose one of the vertices of
the unique triangle containing the center, giving 3C2m+13C_{2m+1} ways.
Equating the two results, we get
(2m+3)i,j,kNi+j+k=mCi+jCi+kCj+k=3C2m+1. (2m + 3) \cdot \sum_{\substack{i,j,k \in \mathbb{N} \\ i+j+k=m}} C_{i+j} C_{i+k} C_{j+k} = 3C_{2m+1}.
Thus, the stated identity holds.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.