title: Finding number of permutations of 'p' numbers that sum to a given number 'n'
body: <p>I am trying to solve a dynamic programming problem and part of the problem involves finding 
  number of permutations of a set of 'p' numbers that will sum up to a number 'n'.
  Each number in the set of p numbers should be between 0 to n inclusive.</p>
  
  <p>For example if n = 4 and p  = 3, I have the following 12 permutations</p>
  
  <pre><code>{4,0,0},{0,4,0},{0,0,4}
  {2,2,0},{2,0,2},{0,2,2}
  {1,3,0},{1,0,3},{0,1,3}
  {1,1,2},{1,2,1},{2,1,1}
  </code></pre>
  
  <p>I started with this DP approach. </p>
  
  <pre><code>n(i,j) represents number of ways of representing n using i,j in p positions 
  </code></pre>
  
  <p>My base case would be </p>
  
  <pre><code>n(i,0) = n(0,i) = p   
  </code></pre>
  
  <p>(for example, n(4,0) in p=3 places is 3 which is {4,0,0},{0,4,0},0,0,4}</p>
  
  <p>recursive case</p>
  
  <pre><code>n(i,j) = n(i,j-1)*n(i-1,j)
  </code></pre>
  
  <p>(example : n(1,2) = n(1,1) * n(0,2)  which recurses to n(1,0) * n(0,1) * 2)</p>
  
  <p>I am not sure if I am proceeding in the right direction as the above approach doesn't lead me to a correct answer. Please guide me in the right direction.</p>