title: Optimal parenthesis for matrix multiplication
body: <p>The statement goes this way (this scenario occurs while choosing which of all matrix pairs to be parenthesized for optimal matrix multiplication)</p>
  
  <p><code>p(n) = Summation of P(k)P(k-n)</code> is <code>Ω(2^n)</code> for <code>k = 1</code> to <code>n - 1</code> and for <code>n&gt; = 2</code>.</p>
  
  <p><code>p(n)</code> is the number of combinations of alternate parenthesis.</p>
  
  <p>Say <code>p(3) = A1(A2*A3)</code> or <code>(A1*A2)A3</code> or <code>(A1*A2*A3)</code>.</p>
  
  <p><code>k</code>: split value.</p>
  
  <p><code>n</code>: number of matrices.</p>
  
  <p>I solved this equation using recursion.</p>
  
  <p>Lets say I have four matrices <code>A1,A2,A3,A4</code>.</p>
  
  <p>Lets say <code>k = 2</code> and we have <code>n = 4</code>.</p>
  
  <p><code>p(4) = p(1)p(3) + p(2)p(2)</code></p>
  
  <p>Solving recursively for <code>p(3)</code> and <code>p(2)</code> we get:</p>
  
  <p><code>p(4) = p(1)p(3) + p(2)p(2) + p(1)p(1)p(2) + p(1)p(2)p(1) + p(1)p(1)p(1)p(1)</code>.</p>
  
  <p>What it implies, is that we can parenthesize <code>A1A2A3A4</code> in the following ways:</p>
  
  <p><code>p(4) = A1(A2A3A4)</code> or <code>(A1A2)(A3A4)</code> or <code>(A1)(A2)(A3A4)</code> or <code>(A1)(A2A3)(A4)</code> or <code>(A1)(A2)(A3)(A4)</code>.</p>
  
  <p>My question is:</p>
  
  <p>if for <code>n = 3</code> <code>p(n) = 3</code> and for <code>n = 4</code> <code>p(n) = 5</code></p>
  
  <p>then how come <code>p(n) = summation of p(k)p(n-k)</code> is  <code>Ω(2^n)</code>?</p>