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?

  • 1
    $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.