Finding number of permutations of 'p' numbers that sum to a given number 'n'

Question

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.

For example if n = 4 and p = 3, I have the following 12 permutations

{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}

I started with this DP approach.

n(i,j) represents number of ways of representing n using i,j in p positions 

My base case would be

n(i,0) = n(0,i) = p   

(for example, n(4,0) in p=3 places is 3 which is {4,0,0},{0,4,0},0,0,4}

recursive case

n(i,j) = n(i,j-1)*n(i-1,j)

(example : n(1,2) = n(1,1) * n(0,2) which recurses to n(1,0) * n(0,1) * 2)

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.

Answer 1

Contrary to my comment, this problem is actually easier to solve if we count the number of sets and the permutations of those sets at the same time.

If we only need to count instead of actually generating each of the sets, we can do so directly with some simple combinatorics. Let's fix p = 3, n = 5 for our example and imagine that we have n = 5 balls:

o o o o o

Now the question is equivalent to, how many ways can we split the balls into groups of 3 where each group can have [0, 5] balls? Imagine if we had p - 1 = 2 sticks that we could individually place anywhere: before all five balls, after all five balls, and between any two balls. For example:

| o o | o o o => (0, 2, 3)
o | | o o o o => (1, 0, 4)
o o o o | | o => (4, 0, 1)

Notice how the questions are equivalent? Anyway we can put those sticks, we can also partition our n balls into p sets. Notice that we only need p - 1 sticks to generate the p numbers (all the balls before the first stick are the first group, all the balls after the last stick are the last group, any balls between two sticks are the other groups).

So now our question is how many ways can I arrange my n balls and p - 1 sticks? You can think of it as having n + (p - 1) slots and you are just picking the n spots for the balls... and the rest are where the sticks go. Thinking of it this way we can apply a basic formula of combinatorics (it's proven using the axiomatic rule of sum and rule of product... not sure I've ever even seen the proof):

(n + (p - 1)) Choose n = (n + (p - 1))! / n! / (p - 1)!

So in our example, it's 7! / 5! / 2! = 21. And you can see that in your example it would be 6! / 4! / 2! = 15. You missed a few permutations (for example, {0, 3, 1}).

You can also solve this with DP by a simple recursive equation. Basically

`f(n, p) = Sum over i = 0 to n, f(n - i, p - 1)`

and memoize some of the values of f. The idea is, you pick the value for the first member of your set S and then the next recursive call picks the next member of S and so on. The base cases would probably be something like f(0, p) = 1 and f(n, 0) = 0 and otherwise you can use the recursive case. The closed form is obviously a lot more performant though if you don't actually need the sets themselves.