## Counting possible parenthesizations in Matrix Chain multiplication

*Problem Statement:* Given the number of matrices involved in a chain matrix multiplication, find out the number of ways in which you can parenthesize these matrices in the multiplication, i.e., you have to find the number of ways you can introduce brackets in this chain matrix multiplication. (forming groups of 2).

For example,

A x B x C can be grouped in 2 ways,

(A x B) x C

A x (B x C)

You should remember that while matrix multiplication is not commutative, it is associative. Hence both the multiplications mean the same.

How do we find the number of such parenthesizations?It becomes simple when you realize that you can derive solutions for this problem using solutions to smaller subproblems which you calculated earlier. Dynamic Programming 🙂So for,

N=1, P(N) = 1

N=2, P(N) = 1 (easy to figure out)

N=3, P(N) = 2 (again easy)

So what we are doing here is finding out the previous solution and figuring out the different ways you can introduce one more matrix in the picture to find the next. So your function looks like,

I guess you understand how this is Dynamic Programming. And also the fact that this is a very simple permutations question. 🙂 Not really a programming problem.

Why did I write this post?There is a genre of DP problems known as Optimal Matrix Chain multiplication. You are supposed to find the way (out of these P(n) ways) in which the number of multiplications required will be the least.We will solve this problem in the next post.

Till then, adios! 🙂

So how do you display all the possible sequence of combination, for a matrix chain given n matrix. Display result as the various parenthesizations