A Number of unequal integers with sum S

AI Thread Summary
The discussion centers on finding the number of ways to select n unequal integers from a set (1 to R) that sum to a specific value S. The original poster has encountered challenges with computational methods for larger numbers and is exploring combinatorial approaches. They provide examples illustrating how the number of valid combinations increases with higher sums. The conversation also touches on the complexities of partitions and the significance of the maximum integer R in the calculations. Ultimately, the goal is to derive a solution that accommodates the constraints of unequal integers while summing to S.
Jarfi
Messages
384
Reaction score
12
TL;DR Summary
Number of unequal numbers with sum S
Hello, I've been trying to solve this problem for a while, and I found a technical solution which is too computationally intensive for large numbers, I am trying to solve the problem using Combinatorics instead.

Given a set of integers 1, 2, 3, ..., 50 for example, where R=50 is the maximum, and a sample of n numbers from this set, what is the number of ways (number of sets) where sum(n) = S

Example:
R=50, n=4, S = 13

1+2+3+7 = 13
1+2+4+6 = 13
1+3+4+5 = 13
is the possible configurations for 13. But for say 16, we could have

1 + 3 + 4 + 8
1+3+5+7
1 + 2 + 5 + 8
1+ 2 + 6 + 7
etc ..

As you can see, the number of equivalent sums increases the higher S becomes.

Before I confuse you with what I tried does anybody have an idea on this ?

Note: partitions are not easily applicable here as we have a special case, where there needs to be x parts, all unequal, no 0s, etc.
 
Last edited:
Physics news on Phys.org
Jarfi said:
Summary:: Number of unequal numbers with sum S

Before I confuse you with I tried does anybody have an idea on this ?
Yes.
 
fresh_42 said:
Yes.
Ok, and?
 
Jarfi said:
Example:
R=50, n=4, S = 13

1 + 2 + 3 + 7 = 13 is the only possible configuration here from my understanding. But for say 16, we could have
What's wrong with:

1 + 2 + 4 + 6 = 13
1 + 3 + 4 + 5 = 13
 
PeroK said:
What's wrong with:

1 + 2 + 4 + 6 = 13
1 + 3 + 4 + 5 = 12
I am not interested in 12 if the goal is to find S = 13 . What is your point ?
 
Jarfi said:
I am not interested in 12 if the goal is to find S = 13 . What is your point ?
That you can't count and I can't type?
 
  • Haha
Likes hutchphd
PeroK said:
That you can't count and I can't type?
I can't count ?
 
Jarfi said:
I can't count ?
1 + 3 + 4 + 5 = 13 (not 12)
 
PeroK said:
1 + 3 + 4 + 5 = 13 (not 12)
See my updated post. There are several sums equivalent to 13, I wasn't being too accurate I concede
 
  • #10
Jarfi said:
See my updated post. There are several sums equivalent to 13, I wasn't being too accurate I concede
Why would your problem be significantly easier than partitions?
 
  • #11
PeroK said:
Why would your problem be significantly easier than partitions?
It is a problem of partitions, restricted unequal partitions into a fixed number of parts, that is. It is harder(computationally) to solve not easier. Thus the partitions approach may not be the most optimal.
 
  • #12
Does the R really matter to you? It's just going to cause weird complications on the split of whether S is larger or smaller than R.
 
  • #13
Office_Shredder said:
Does the R really matter to you? It's just going to cause weird complications on the split of whether S is larger or smaller than R.
The R matters yes, It is not the most complicated thing though the complication is that the samples should be unequal and restricted into a fixed number of parts.

S is the Sum
s is a sample from 1:50 or 1:R
n is the number of samples ( s(1), s(2), ..., s(n) where sum(s) = S )

Nr sets where s(i) < R for all i, are allowed. But we could also calculate this
Nsets with s(i) < R for all i =
Nsets ALL with any Natural Number s(i) -
Nsets with s(i) > R for at least one i


if it simplifies things.

Anyway if we can solve the problem without the size limit of R (Nsets ALL) the problem can be solved for the special case of s(i) < R
 
Back
Top