MCM question

Question

Comments

33) no. of orderings = $C_{n-1}$(Catalan number)$ =  \frac{2n!}{(n+1)!n!} = C_3 =  \frac{6!}{4!3!} = 5$.

5 different orderings = 5 different parenthesizations

• (A1(A2(A3A4)))

• ((A1A2)(A3A4))

• (((A1A2)A3)A4)

• ((A1(A2A3))A4)

• (A1((A2A3)A4))

34) https://gateoverflow.in/57553/minimum-number-multiplications-required-compute-matrices

Answer 1

The number of valid ways to fully parenthesize a product of \( n \) matrices is given by the Catalan number:

\[C_{n-1} = \frac{(2(n-1))!}{(n-1)! (n)!}\]

\( n = 4 \),

\[C_3 = \frac{(2 \times 3)!}{3! \times 4!} = \frac{6!}{3! \times 4!} = \frac{720}{6 \times 24} = 5\]

---

 

Maximum number of multiplications: \[ ((A_1 \times (A_2 \times A_3)) \times A_4) = 100 \times 5 \times 50 + 10 \times 100 \times 50 + 10 \times 50 \times 1 \] \[ = 25000 + 50000 + 500 = 75,500 \]