Number of unequal integers with sum S

[Jarfi]

TL;DR

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.

 

[fresh_42]

Summary:: Number of unequal numbers with sum S

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

Yes.

 

[Jarfi]

Yes.

Ok, and?

 

[PeroK]

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

 

[Jarfi]

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 ?

 

[PeroK]

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?

 

[Jarfi]

That you can't count and I can't type?

I can't count ?

 

[PeroK]

I can't count ?

1 + 3 + 4 + 5 = 13 (not 12)

 

[Jarfi]

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

 

[PeroK]

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?

 

[Jarfi]

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.

 

[Office_Shredder]

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.

 

[Jarfi]

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