1
$\begingroup$

If I have for example 3 variables, and I need them to add to specific total, say 6, how do I calculate the number of combinations that will add to 6. Like 1+1+4=6 and 1+4+1=6 and 2+2+2=6 and 1+2+3=6 etc.

Is there a formula I can use? What if I am using say 10 variables with ranges from say 1 to 1000 and the total is for example 8063?

Thanks

$\endgroup$

1 Answer 1

2
$\begingroup$

You're trying to find the number of integer solutions to the problem: $$x_1+...+x_k=n, \ \ \ x_i\geq a$$ The general formula for number of solutions is $ {n-ak+k-1 \choose k-1}$. For three variable case, and positive integers as in your example, we have $k=3,a=1,n=6$, which yields ${5 \choose 2}=10$ solutions. Specifically, they are $\{(1,1,4),(1,4,1),(4,1,1),(2,2,2),\underbrace{(1,2,3)}_{6 \ \text{permutations}}\}$.

The logic is simple. Let's say you want to solve $x_1+x_2+x_3=6,\ \ x_i\geq 0$. Each solution corresponds to a permutation of chracters ||111111, e.g. 11|111|1 corresponds to $x_1=2,x_2=3,x_3=1$. So, we'll use $n$ number of $1$'s and $k-1$ number of separators, which yields a total of ${n+k-1 \choose k-1}$ permutations. A small extension is adding non-zero constraints, e.g. $x_i\geq 1$. Then, we first throw $1$'s into the variables, and allocate the remaining 1's. We can work out the formula for the general case, following the example.

$\endgroup$
3
  • $\begingroup$ Could you provide a reference for the general formula you post or derive it. $\endgroup$
    – Jim
    Sep 6, 2019 at 17:08
  • $\begingroup$ I've added some explanation. I didn't get it from anywhere. $\endgroup$
    – gunes
    Sep 6, 2019 at 17:21
  • $\begingroup$ Awesome. Thanks so much. You explained it very well. $\endgroup$ Sep 7, 2019 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.