Question

Matrix chain multiplication how many ways matrices can be arranged

Answer 1

Say I have 4 matrices A,B,C,D I can multiply them like this

((AB)C)D = (A(BC))D = (AB)(CD) = A((BC)D) = A(B(CD))

So, how many ways can n matrices be multiplied?

I thought it should be C(n+1,n) Because there are n matrices and we are putting the brackets in n+1 boxes then I realised that multiple brackets can reside in the same box.

I found another answer (1/n)C(2(n-1),n-1) however I dont know how this works

Answer 2

these correspond to the different ways that parentheses can be placed to order the multiplications for a product of 5 matrices.

hope it helps you