# Number of parenthesizations and Catalan numbers

I read in CLRS that the number of possible parenthesizations for a product of $$n$$ matrices is given by the recursive formula:

$$P(n)= \begin{cases} 1 & \text{if } n = 1,\\ \sum^{n-1}_{k=1} P(k)P(n-k) & \text{if } n \ge2. \end{cases}$$

This comes from the following two facts:

• For $$n=1$$ there is only only item, so only one way to fully parenthesize a matrix product.
• For $$n\geq2$$ a fully parenthesized matrix product is the product of two fully parenthesized subproducts, and the split between the two subproducts may occur between the $$k$$th and $$(k+1)$$st matrices for any $$k=1,2,\ldots, n-1$$.

So far so good.

Now, I know that $$\sum^{n-1}_{k=1} P(k)P(n-k)$$ has a strong relationship with Catalan numbers, and I'm hoping to establish that relationship with precision.

For background, Catalan numbers are defined as a sequence of the following form:

$${\displaystyle C_{0}=1\quad {\text{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0,}$$

where a term in the sequence is also known to follow the alternative expression: $$C_n={\tfrac {1}{n+1}}{\tbinom {2n}{n}}.$$

Expressing the original recurrence in terms of Catalan numbers shouldn't be hard, but the differences in summation and sequence indices are making it difficult for me. What's a good way to rearrange these types of Eqs. to re-express e.g. the first Eq. as a function of the second one?

• A good way to see what's going on is to calculate a few values of the $P$ sequence and compare it to the known values of the $C$ sequence. The connection would become apparent immediately. – Yuval Filmus Apr 11 '20 at 8:10

Define function $$Q:\mathbb N\to\mathbb N$$ such that $$Q(n)=P(n+1)$$ for all $$n\ge 0$$. Or, what is equivalent, $$P(n)=Q(n-1)$$ for all $$n\ge 1$$.
We have $$Q(0)= P(0+1)=P(1)=1.\quad\quad\quad\quad\quad\quad\quad\quad$$
Also, for $$n\ge0$$, \begin{aligned} Q(n+1)&=P(n+2)\\ &=\sum^{(n+2)-1}_{k=1} P(k)P((n+2)-k)\\ &=\sum^{n+1}_{k=1} Q(k-1)Q(n+1-k)\\ &\stackrel{k=i+1}{=\!=\!=\!=}\sum^{n}_{i=0} Q((i+1)-1)Q(n+1-(i+1))\\ &=\sum^{n}_{i=0} Q(i)Q(n-i).\\ \end{aligned}
We see that $$Q(\cdot)$$ and the Catalan numbers $$C(\cdot)$$ share the same initial condition and the same recurrence relation. So, we have, for all $$n\ge0$$, $$Q(n) = C(n).$$ So, for all $$n\ge 1,$$ $$P(n)=Q(n-1)=C(n-1)={\tfrac {1}{n}}{\tbinom {2(n-1)}{n-1}}$$
Exercise. Define function $$D$$ such that $$D(n)=C(n-1)$$ for $$n\ge1$$. Show that $$D(n)=P(n)$$ for $$n\ge1$$, assuming that you have not seen the deduction above.