# In how many different ways can we fully parenthesize the matrix product?

We have a finite number of matrices that we wish to compute the product of . Say we wish to compute a product of n matrices and we have the subroutine to compute a pair of matrices . We also know that matrix products are associative ie :

$\left({\mathbf A \mathbf B}\right) \mathbf C$ and $\mathbf A \left({\mathbf B \mathbf C}\right)$ are same .

$$A_1A_2A_3...A_n$$

So what are the number of ways in which we can parenthesize the product ?

-
I don't think that the fact that the factors are matrices is relevant to this question. May I remove the "matrices" tag? –  Marc van Leeuwen Sep 3 '12 at 11:46
@MarcvanLeeuwen sure you can .But I encountered this problem while trying to find out the productof matrices –  Geek Sep 3 '12 at 11:47

If you have $n+1$ matrices, the number of ways is the Catalan number $C_n$. The number $C_n$ is given by the explicit formula $$C_n=\frac{1}{n+1}\binom{2n}{n}.$$ This particular example is the third one in the aticle linked to, in the "Applications to Combinatorics" part. It is not hard to verify that the number of ways to parenthesize $n+1$ matrices (or a product of any kind) satisfies the basic recurrence for the Catalan numbers.
@DennisGulko: It seems that the OP intended to demonstrate associativity in $(AB)C=A(BC)$, and not to indicate that these two different ways of parenthesizing should be counted only once. –  Teddy Sep 3 '12 at 10:21