How do you calculate the number of combinations using unique numbers that equal a specific sum?

Question

Hello I need help with a problem that I cannot find in any google searches. I am trying to work out how many possible unique combinations of 6 unique numbers from 1 to 49 will produce a specified sum. The criteria is as follows:

• Order of the digits unimportant
• Each of the 6 digits must be unique
• I don't need to know what the combinations are because it would be in the millions I can work out the smallest and largest sums through trial and error but the number of possible configurations grows rapidly as the sum approaches 150. Sum 21 = 1+2+3+4+5+6 = 1 possible combination Sum 22 = 1+2+3+4+5+7 = 1 Sum 23 = 1+2+3+4+N5+N6 = 2 Sum 24 = 1+2+3+4+N5+N6 = 2 .... Sum 150 = N1+N2+N3+N4+N5+N6 = ???

Any help on this matter would be greatly appreciated.

Answer 1

Consider the following problem:

Any unique combination of $6$ distinct positive integers can be ordered in ascending order, so that (for example)

$$a_1 < a_2 < a_3 < a_4 < a_5 < a_6$$

where $$a_1 + \cdots + a_6 = N.$$

Define:
$x_1 = a_1.$
$r_i = a_{i+1} - a_i ~: ~i \in \{1,2,3,4,5\}.$

Then

$a_1 = x_1.$
$a_2 = x_1 + r_1.$
$a_3 = x_1 + r_1 + r_2.$
$a_4 = x_1 + r_1 + r_2 + r_3.$
$a_5 = x_1 + r_1 + r_2 + r_3 + r_4.$
$a_6 = x_1 + r_1 + r_2 + r_3 + r_4 + r_5.$

Therefore,

$N = a_1 + \cdots + a_6 = 6x_1 + 5r_1 + 4r_2 + 3r_3 + 2r_4 + r_5,$
subject to the following constraint:

• $x_1, r_1, \cdots, r_5~$ are all positive integers.

This variation of Stars and Bars problems has been discussed often at MathSE. To the best of my knowledge, there is no shortcut to the following brute force:

For $d \in \Bbb{R^+},~$ let $~\lfloor d\rfloor$ (i.e. the floor function) represent the largest integer $~\leq d$.

For $~n,k \in \Bbb{Z^+}~$ let $~f(n,k)~$ denote $~\displaystyle \left\lfloor\frac{n}{k}\right\rfloor.$

Let $S_2(n)$ denote the number of positive integer solutions to

• $2r_2 + r_1 = n \implies S_2(n) = f(n-1,2)$.
• Note that $S_2(2) = 0.$

Let $S_3(n)$ denote the number of positive integer solutions to

• $~\displaystyle 3r_3 + 2r_2 + r_1 = n \implies S_3(n) = \sum_{r_3 = 1}^{f(n,3)} S_2(n - 3r_3).$
• Note that $S_3(3) = 0.$

Let $S_4(n)$ denote the number of positive integer solutions to

• $~\displaystyle 4r_4 + 3r_3 + 2r_2 + r_1 = n \implies $
  $\displaystyle S_4(n) = \sum_{r_4 = 1}^{f(n,4)} S_3(n - 4r_4).$

Let $S_5(n)$ denote the number of positive integer solutions to

• $~\displaystyle 5r_5 + 4r_4 + 3r_3 + 2r_2 + r_1 = n \implies $
  $\displaystyle S_5(n) = \sum_{r_5 = 1}^{f(n,5)} S_4(n - 5r_5).$

Let $S_6(N)$ denote the desired enumeration, which is the number of positive integer solutions to

• $~\displaystyle 6x_1 + 5r_5 + 4r_4 + 3r_3 + 2r_2 + r_1 = N \implies $
  $\displaystyle S_6(N) = \sum_{x_1 = 1}^{f(N,6)} S_5(N - 6x_1).$

As I say, this problem has been discussed before on MathSE. There may be a better approach, which involves generating functions, which I know nothing about. However, it is reasonable to exclude any computer aided solution, such as computing the coefficient to a certain term in a certain polynomial. That is, you could just as easily write a computer program to employ the algorithm outlined above.

Given the exclusion of computer aids, it will be interesting to see how a generating function approach compares with the above algorithm.

---

Edit
If all that you are looking for is a chart of $S_6(N),$ for various values of $N$, then I recommend writing a computer program in some language like Python, C, or Java, that employs the algorithm above. Alternatively, there may be an algorithm based on generating functions that is easier to program.

Edit
See also the comment of user15343006, following this answer. He indicated that I had forgotten the constraint that none of $x_1, x_2, \cdots, x_6$ may be larger than $49$.

When the constraints are translated from $[x_1, x_2, \cdots, x_6]$ to $[x_1, a_1, \cdots, a_5]$, then the added constraint is translated to :

• $x_1 + a_1 + a_2 + a_3 + a_4 + a_5 \leq 49.$