title: Number of combinations for 4xN domino bricks
body: <p>I want to find the number of possible different combinations for a 4 x N area (4 units width and N units height, N &ge; 1) of domino bricks <em>using dynamic programming</em> .</p>
  
  <p>Domino bricks have a size of 2x1 e.g.</p>
  
  <pre><code>==
  </code></pre>
  
  <p>for a horizontal and</p>
  
  <pre><code>|
  |
  </code></pre>
  
  <p>for a vertical brick.</p>
  
  <p>Now, </p>
  
  <p>Example 4x1 (two domino bricks beneath each other)</p>
  
  <pre><code>====
  </code></pre>
  
  <p>Examples for 4x2 brick configurations (5 in total)</p>
  
  <p>1)</p>
  
  <pre><code>||||
  ||||
  </code></pre>
  
  <p>2) (Turn two bricks on the right)</p>
  
  <pre><code>||==
  ||==
  </code></pre>
  
  <p>3) </p>
  
  <pre><code>|==|
  |==|
  </code></pre>
  
  <p>4)</p>
  
  <pre><code>====
  ====
  </code></pre>
  
  <p>5)</p>
  
  <pre><code>==||
  ==|| 
  </code></pre>
  
  <p>Number of unique combinations known so far</p>
  
  <pre><code>4x1 : 1 possibility
  4x2 : 5 possibilites
  4x3 : 11 possibilites
  4x4 : 36 possibilites
  </code></pre>