Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a number sequence from 1 to 100. Given 2 bins, the numbers are randomly assigned to each bin.

I know the total sum from 1 to 100 is 5050. Thus, for both bins to have the same sum, each bin must sum up to 2525. All the 100 numbers must belong to either bin.

I know there are a total of 2^100 possible combinations. How do I find the number of combinations that sum to 2525 in each bin?

Thank you.

EDIT: Just to clarify, a bin is just a collection of numbers. So essentially, I have collection A and collection B. The sum in each collection must be equal and all 100 numbers must belong to either collection. Think of them as buckets or whatever is convenient for explanation.

share|improve this question
2  
@lone. If you can develop a program, the recursion $f(n,S) = f(n-1,S)+f(n-1,S-n)$ will do it –  Bilou06 Mar 17 at 9:38
1  
@lone: Regarding Bilou06's recursion: For this problem, dynamic programming (or memoization) is absolutely essential, or else you'll end up repeating a lot of work and likely take years to finish computing (if you don't run out of stack space earlier). Basically, instead of writing a recursive function, you should create a 2D array, fill in some initial entries, and loop through the entries. –  Tony Mar 17 at 9:58
1  
Note: Spreadsheets can be used for double-recursion –  Mark Bennet Mar 17 at 10:05
1  
To fill the array, you may use properties such as $n \geq s\implies f(n,s)=f(s,s)$ –  Bilou06 Mar 17 at 10:12
1  
You're right, $2^{100}$ is completely beyond any computer's ability to process in a reasonable amount of time. However, you're not actually going through all of them. This is the beauty of algorithms. –  Tony Mar 17 at 10:23

2 Answers 2

up vote 3 down vote accepted

Using the recursion (thanks Bilou06)

$$f(n, S) = f(n - 1, S) + f(n - 1, S - n),$$

we have the following Python code:

n = 100
S = 2525

matrix = [[0]*(S+1) for x in range(0, n+1)]

for S in range(0, S+1):
    matrix[0][S] = 0
for n in range(0, n+1):
    matrix[n][0] = 1
for n in range(1, n+1):
    for S in range(S+1):
        matrix[n][S] = matrix[n-1][S] + matrix[n-1][S-n]

print matrix[n][S]

You can change the values of n and S when running the code to verify they work for smaller cases.

share|improve this answer
    
$1731024005948725016633786324$ is a very good answer. Next question: any idea what this is? I mean, a proper value in terms of binomial coefficients/power? –  Sabyasachi Mar 17 at 10:44
    
The prime factorization is $2^2 \times 61 \times 1044041 \times 6795097778839840081$. Not sure what this means though. –  Tony Mar 17 at 10:48
    
I'm also curious to know what the number means. I know if i test with n=4 and S=5, i get 2, which is correct since there are only 2 combinations that sum to 5. What other meanings can the answer have? –  lone Mar 17 at 10:57
    
I have a question regarding the values obtained at the final row. At each step, the calculation considers S ways to choose n-1 and S-n ways to choose n-1. What is the significance of the result obtained in the last row? if a n of 3 is used, my last row is [2, 2, 2, 2]. –  lone Mar 18 at 15:18

i converted the code to c code. however, my code would just hang.

i tried this with a smaller value of n =15. but my c code produces 5505 instead of the 722 this python code produced.

#include <stdio.h>
#include <string.h>
#include <math.h>  main() 
{ 
 int n=100; 
 double k=2; 
 int min=2525; 
 int rec[100][2525]; //100 row, 2525 column
 int x,y,r,c,str; 
 int po = (int) pow((double) k,n); //2^100

for (r=0;r<n+1;r++) {
    for(c=0;c<min+1;c++)
    {
        rec[r][c]=0;
    } } for (x=0;x<n+1;x++) {
    rec[x][0]=1; }

for (y=0;y<min+1;y++) {
    rec[0][y]=0; }

for (r=1;r<n+1;r++) {
    for(c=0;c<min+1;c++)
    {
        rec[r][c]=rec[r-1][c]+rec[r-1][c-r];
    } }

printf("%d, %d, %d\n",rec[100][2525],r,c); printf("%d", po ); scanf ("%d",str); }
share|improve this answer
    
If you expect someone to help you with your code, you could pay attention to make it as readable as possible. What is tt? Besides, rec[0][0] should be 1, as in he python code –  Bilou06 Mar 19 at 8:27
    
rec[100][2525] is not a valid statement. If you define "int x[123]" the maximal element you can access is "x[122]". –  Listing Apr 7 at 18:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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