[問題] 矩陣連乘的所有可能組合個數

[han98115 (han)]

請問n個矩陣連乘的所有可能組合個數為什麼是(1/n)*(C的2(n-1)取(n-1))
ex. n=3   (M_1*M_2)*M_3      M_1*(M_2*M_3)  ............2種

    n=4   M_1*(M_2*(M_3*M_4))     M_1*((M_2*M_3)*M_4)
          (M_1*M_2)*(M_3*M_4)     (M_1*(M_2*M_3))*M_4
          ((M_1*M_2)*M_3)*M_4               ............5種

請問那個公式是怎麼想出來的

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.137.49.3
→ tkcn:Catalan number, 可參考 wikipedia 或 CLRS
推 DJWS:找出recurrence relation 再用generating function轉成一般型