A Number of unequal integers with sum 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