Number of parenthesizations and Catalan numbers

Question

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?

Answer 1

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.