title: Calculating the number of paths through graph
body: <p>I am looking the number of unique <em>x</em> length paths through a graph starting at a particular node.</p>
  
  <p>However I have a restriction that no node is visited more than once on any path.</p>
  
  <hr>
  
  <p>For example take the following graph:<br>
  <img src="https://i.imgur.com/XysqM.png" alt="enter image description here"></p>
  
  <p>If I am after the number of 3 length paths starting at 5.</p>
  
  <p>The answer would be 9.</p>
  
  <pre><code>5 -&gt; 2 -&gt; 1 -&gt; 3
  5 -&gt; 2 -&gt; 4 -&gt; 3
  5 -&gt; 2 -&gt; 4 -&gt; 7
  5 -&gt; 4 -&gt; 2 -&gt; 1
  5 -&gt; 4 -&gt; 3 -&gt; 1
  5 -&gt; 4 -&gt; 7 -&gt; 6
  5 -&gt; 6 -&gt; 7 -&gt; 4
  5 -&gt; 7 -&gt; 4 -&gt; 2
  5 -&gt; 7 -&gt; 4 -&gt; 3
  </code></pre>
  
  <p>Note I am only concerted with the answer (9) <strong>not the specific paths</strong>.</p>
  
  <hr>
  
  <p>I have tried using an <a href="http://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow noreferrer">adjacency matrix</a> to the power of <em>x</em> to give the number of paths, but I cannot work out how to account for unique node restriction.</p>
  
  <p>I have also tried using a <a href="http://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow noreferrer">depth-first search</a> but the amount of nodes and size of <em>x</em> makes this infeasible.</p>
  
  <hr>
  
  <p>EDIT: Confused DFS with BFS (Thank you Nylon Smile &amp; Nikita Rybak).</p>