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?