Counting the number of parenthesization

I'm reading CLRS and there is something I don't understand regarding counting the number of parenthesization, in the Matrix-chain multiplication chapter, the book says:

Denote the number of alternative parenthesizations of a sequence of $$n$$ matrices by $$P(n)$$. When $$n$$ = 1, we have just one matrix and therefore only one way to fully parenthesize the matrix product. When $$n$$ $$\geq$$ 2, a fully parenthesized matrix product is the product of two fully parenthesized matrix subproducts, and the split between the two subproducts may occur between the $$k$$th and ($$k$$ + 1)st matrices for any $$k$$ = 1, 2, ..., $$n$$ - 1.

what I don't understand is the the part about the split? what exactly does it mean to split the two subproducts?

The split in a product is between the two outermost pairs of parantheses. For example, in $$((a*b)*(c*d))*(e*f)$$, the split is between the $$d$$ and $$e$$ because the last multiplication that is performed is between the results of the products $$abcd$$ and $$ef$$. The split tells you where the last multiplication is performed and let’s you decompose the problem into two subproblems.

• I understand, thank you. Jun 9, 2022 at 18:54

Suppose you have $$n$$ matrices $$M_1, M_2, …, M_n$$.

The product of all matrices is $$M_1\times M_2\times…\times M_n$$ and since the matrix product is associative, there is no need for parentheses from a mathematical point of view.

However, from a complexity perspective, the product may not takes the same amount of computation time if you compute $$M_1\times (M_2\times … \times M_n)$$ or $$(M_1\times M_2)\times (M_3\times…\times M_n)$$ and so on.

For example, using the naive matrix multiplication algorithm, if $$n = 3$$ and the dimensions of $$M_1$$ are $$10 \times 100$$, the dimensions of $$M_2$$ are $$100\times 5$$ and the dimensions of $$M_3$$ are $$5\times 2$$, then computing $$M_1\times (M_2\times M_3)$$ uses $$100\times 5 \times 2 + 10 \times 100 \times 2 = 3000$$ scalar multiplications, but computing $$(M_1\times M_2)\times M_3$$ uses $$10\times 100 \times 5 + 10 \times 5 \times 2 = 5100$$ scalar multiplications.

The split the book is talking about is about the position of the parentheses in the computation, separating the computation of $$n$$ matrices into the product of two matrices, the first one being the result of $$M_1\times … \times M_k$$ and the second one of $$M_{k+1}\times …\times M_n$$, for a certain $$k\in \{1, …, n-1\}$$.

• I understand, thank you. Jun 9, 2022 at 18:53