Number of possible combinations

Question

How many possible combinations of the variables a,b,c,d,e are possible if I know that:

a+b+c+d+e = 500

and that they are all integers and >= 0, so I know they are finite.

Answer 1

If they are a real numbers then infinite ... otherwise it is a bit trickier.

(OK, for any computer representation of a real number there would be a finite count ... but it would be big!)

Answer 2

One way of looking at the problem is as follows:

First, a can be any value from 0 to 500. Then if follows that b+c+d+e = 500-a. This reduces the problem by one variable. Recurse until done.

For example, if a is 500, then b+c+d+e=0 which means that for the case of a = 500, there is only one combination of values for b,c,d and e.

If a is 300, then b+c+d+e=200, which is in fact the same problem as the original problem, just reduced by one variable.

Note: As Chris points out, this is a horrible way of actually trying to solve the problem.

link text

Answer 3

Including negatives? Infinite.

Including only positives? In this case they wouldn't be called "integers", but "naturals", instead. In this case... I can't really solve this, I wish I could, but my math is too rusty. There is probably some crazy integral way to solve this. I can give some pointers for the math skilled around.

being x the end result, the range of a would be from 0 to x, the range of b would be from 0 to (x - a), the range of c would be from 0 to (x - a - b), and so forth until the e.

The answer is the sum of all those possibilities.

I am trying to find some more direct formula on Google, but I am really low on my Google-Fu today...

Answer 4

The answer to your question is 2656615626.

Here's the code that generates the answer:

public static long getNumCombinations( int summands, int sum )
{
 if ( summands <= 1 )
  return 1;
 long combos = 0;
 for ( int a = 0 ; a <= sum ; a++ )
  combos += getNumCombinations( summands-1, sum-a );
 return combos;
}

In your case, summands is 5 and sum is 500.

Note that this code is slow. If you need speed, cache the results from summand,sum pairs.

I'm assuming you want numbers >=0. If you want >0, replace the loop initialization with a = 1 and the loop condition with a < sum. I'm also assuming you want permutations (e.g. 1+2+3+4+5 plus 2+1+3+4+5 etc). You could change the for-loop if you wanted a >= b >= c >= d >= e.

Answer 5

I solved this problem for my dad a couple months ago...extend for your use. These tend to be one time problems so I didn't go for the most reusable...

a+b+c+d = sum

i = number of combinations

        for (a=0;a<=sum;a++)
        {
            for (b = 0; b <= (sum - a); b++)
            {
                for (c = 0; c <= (sum - a - b); c++)
                {
                    //d = sum - a - b - c;
                    i++
                }
            }
        }

Answer 6

@Torlack, @Jason Cohen: Recursion is a bad idea here, because there are "overlapping subproblems." I.e., If you choose a as 1 and b as 2, then you have 3 variables left that should add up to 497; you arrive at the same subproblem by choosing a as 2 and b as 1. (The number of such coincidences explodes as the numbers grow.)

The traditional way to attack such a problem is dynamic programming: build a table bottom-up of the solutions to the sub-problems (starting with "how many combinations of 1 variable add up to 0?") then building up through iteration (the solution to "how many combinations of n variables add up to k?" is the sum of the solutions to "how many combinations of n-1 variables add up to j?" with 0 <= j <= k).

public static long getCombos( int n, int sum ) {
  // tab[i][j] is how many combinations of (i+1) vars add up to j
  long[][] tab = new long[n][sum+1];
  // # of combos of 1 var for any sum is 1
  for( int j=0; j < tab[0].length; ++j ) {
    tab[0][j] = 1;
  }
  for( int i=1; i < tab.length; ++i ) {
    for( int j=0; j < tab[i].length; ++j ) {
      // # combos of (i+1) vars adding up to j is the sum of the #
      // of combos of i vars adding up to k, for all 0 <= k <= j
      // (choosing i vars forces the choice of the (i+1)st).
      tab[i][j] = 0;
      for( int k=0; k <= j; ++k ) {
        tab[i][j] += tab[i-1][k];
      }
    }
  }
  return tab[n-1][sum];
}

$ time java Combos
2656615626

real    0m0.151s
user    0m0.120s
sys 0m0.012s

Answer 7

This would actually be a good question to ask on an interview as it is simple enough that you could write up on a white board, but complex enough that it might trip someone up if they don't think carefully enough about it. Also, you can also for two different answers which cause the implementation to be quite different.

Order Matters
If the order matters then any solution needs to allow for zero to appear for any of the variables; thus, the most straight forward solution would be as follows:

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 0; a <= 500; a++) {
            for (int b = 0; b <= (500 - a); b++) {
                for (int c = 0; c <= (500 - a - b); c++) {
                    for (int d = 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

Which returns 2656615626.

Order Does Not Matter
If the order does not matter then the solution is not that much harder as you just need to make sure that zero isn't possible unless sum has already been found.

public class Combos {
    public static void main() {
        long counter = 0;

        for (int a = 1; a <= 500; a++) {
            for (int b = (a != 500) ? 1 : 0; b <= (500 - a); b++) {
                for (int c = (a + b != 500) ? 1 : 0; c <= (500 - a - b); c++) {
                    for (int d = (a + b + c != 500) ? 1 : 0; d <= (500 - a - b - c); d++) {
                        counter++;
                    }
                }
            }
        }
        System.out.println(counter);
    }
}

Which returns 2573155876.