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$
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 '19 at 17:08
  • $\begingroup$ I've added some explanation. I didn't get it from anywhere. $\endgroup$ – gunes Sep 6 '19 at 17:21
  • $\begingroup$ Awesome. Thanks so much. You explained it very well. $\endgroup$ – Stefan Foot Sep 7 '19 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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