Partitioning an Integer into 9 non-negative integers with limits

Question

There's an equation: 1a + 2b + 3c + 4d ... + 9i = 9

Constraints: 1 <= a + b + c + ... + i <= 10⁴

where a,b,..,i are non-negative integers and each of the integers have a particular range.

For example: 1 <= a <= 5, 2 <= b <= 3, and so on.

I need to find out the number of different sets of values of those variables, or simply, the number of ways of solving that equation.

There's a recursive method of solving this, but that's very slow. I'm unable to think of a way to solve this efficiently under the given constraint.

Answer 1

If you think about it, the solutions are actually very limited.

Since all numbers are non-negative, and you have:

1a + 2b + 3c + 4d ... + 9i = 9

This implies that:

0 <= a <= 9
0 <= b <= 4
0 <= c <= 3
0 <= d <= 2
0 <= e <= 1
0 <= f <= 1
0 <= g <= 1
0 <= h <= 1
0 <= i <= 1

That is, there are only 10*5*4*3*2*2*2*2*2 = 19200 cases to consider.

You can iterate through these cases and find out which ones satisfy your other constraints and which ones have

1a + 2b + 3c + 4d ... + 9i = 9

Hint: start by giving values from i to a. This way, a high value of i or h for example, immediately reduces the possible range of values of the smaller numbers.

---

Make sure you apply MSalters' method before computing. Even though in this case it is not necessary, since the problem is too easy, but in general it helps a lot.

Answer 2

You'd basically want to substitute the variables for which the range is restricted, so a' = a+1, 0 <= a' <= 4 and b' = b+2, 0 <= b' <= 1. Starting at zero makes the math easier. It also allows you to rewrite the equation as 1a' + 2b' + ... + 9i = 4. Since all terms are non-negative, this greatly restricts the search space. For instance, it means that e up to i must all be 0. This reduces the equation to just `1a' + 2b' + 3c + 4d = 4.

Answer 3

Another solution would be to solve 1a + 2b + 3c + 4d ... + 9i = 1 (trivial) and the find all solutions for 1a + 2b + 3c + 4d ... + 9i = N+1 given the solution for 1a + 2b + 3c + 4d ... + 9i = N. That's basically a => a+1 or a=>a-1, b=>b+1 or b=>b-1, c=>c+1 etc.

This is nicely recursive, but only takes 8 iterations to get to N=9 and in each iteration you're just incrementing or decrementing 9 variables.