Question

Number of ways to multiply n matrices formula

Answer 1

do we multiply \(n\) matrices?

Answer 2

The question asks for the number of ways to multiply the n matrices.

for e.x:

ABC = (AB)C = A(BC) (Number of ways = 2)

Answer 3

https://en.wikipedia.org/wiki/Catalan_number

Answer 4

Thanks.

Answer 5

but I got a question, can I use this formula ?

Combination of (number of choices) choose (two) = result
result - 1

Answer 6

I feel the purpose of the question is to derive that formula, not simply to use it...

Answer 7

If so, I won't be able to prove your formula ( I won't copy & paste proof of course). well, how about this ? how to prove it ?

https://allaboutalgorithms.files.wordpress.com/2011/11/parenthesis.jpg?w=595

Answer 8

Using a reasoning from statistical mechanics, I got this result:
\[\Large \frac{{\left( {2n - 2} \right)!}}{{n!\left( {n - 1} \right)!}}\]
it works for \(n=1,2\)

Answer 9

where, of course, \(n\) is the number of the involved matrices

Answer 10

n = 3 , result = 2
n = 4, result = 5
Check your formula.

Answer 11

for \(n=4\), we get:
\[\Large \frac{{\left( {2n - 2} \right)!}}{{n!\left( {n - 1} \right)!}} = \frac{{\left( {8 - 2} \right)!}}{{4! \cdot 3!}} = \frac{{6!}}{{4! \cdot 6}} = \frac{{4! \cdot 5 \cdot 6}}{{4! \cdot 6}} = 5\]

Answer 12

whereas for \(n=2\), we get:
\[\Large \frac{{\left( {2n - 2} \right)!}}{{n!\left( {n - 1} \right)!}} = \frac{{\left( {4 - 2} \right)!}}{{2! \cdot 1!}} = \frac{{2!}}{{2 \cdot 1}} = \frac{2}{2} = 1\]

Answer 13

finally, for \(n=3\), we can write:
\[\Large \frac{{\left( {2n - 2} \right)!}}{{n!\left( {n - 1} \right)!}} = \frac{{\left( {6 - 2} \right)!}}{{3! \cdot 2!}} = \frac{{4!}}{{12}} = \frac{{24}}{{12}} = 2\]

Answer 14

Awesome! nice indeed.

Answer 15

Is there a way to verify if it will lag in bigger numbers ?

Answer 16

How about verifying it using this formula ? https://allaboutalgorithms.files.wordpress.com/2011/11/parenthesis.jpg?w=595

Answer 17

I don't know. I have used the same reasoning in order to get the \(Bose-Einstein\) statistics

Answer 18

Bose - Einstein ? what is that ?

Answer 19

it is a topic of Statistical Mechanics!

Answer 20

So it's right :),

Answer 21

if we make this variable change:
\(m=n-1\), we get:
\[\huge \frac{{\left( {2n - 2} \right)!}}{{n!\left( {n - 1} \right)!}} = \frac{{\left( {2m} \right)!}}{{\left( {m + 1} \right)!m!}}\]
namely, the same formula of @ganeshie8

Answer 22

It's better for on the fly questions , Thanks a lot.

Answer 23

:)