Number of ways to add multiples of numbers from a set of k numbers while all numbers are never multiplied.

I am trying to come up with a general formula. First let me give a simple example.

Let there be 3 numbers: a, b, and c.

I multiply any two of them to get:

3. c*a .......[A]

Exactly three ways to multiply any two of them. Right! Next I add any two of above without repetition. I get:

6. b*c + c*a

Hence I get 3 combinations. Please observe that I added the a*b to all the multiples in [A] until I exhausted all the combinations. Only then I chose b*c. Next I add all of the results in [A] to get:

7. a*b + b*c + c*a

Now I stop. In total, I get 7 combinations.

Let me try with 4 numbers, say a, b, c, and d.

There are four ways to multiply any three of four numbers. Right! I multiply any three of four numbers to get:

4. d*a*b ......[B]

Next I add any two of above without repetition. I get:

10. c*d*a + d*a*b

Hence I get 6 combinations. Please observe that I added a*b*c to all the multiples until I exhausted all the combinations. Only then I chose b*c*d and later c*d*a. Next I add any 3 in [B] to get:

14. b*c*d + c*d*a + d*a*b

I get 4 such additions. No more. Right! Lastly I add all four in [B] to get:

15. a*b*c + b*c*d + c*d*a + d*a*b

Now I stop. In total, I get 15 combinations with 4 numbers.

I can multiply any of (k-1) numbers in the set to get exactly k multiples. Hence k combinations.

Next I choose the first multiple and add it to remaining (k-1) multiples to get (k-1) combinations for addition. I already got all the possible additions with the first multiple. So I strike out the first multiple. Now I chose the second multiple and add it to remaining (k-2) multiples to get (k-2) combinations of addition. Now I strike out the second multiple. I continue with the remaining (k-3) multiples and so on..

I get following number of combinations: (k-1) + (k-2) + (k-3) + ... + (k - (k-1)) = k*(k - 1) - (1 + 2 + 3 + ... + (k-1)) = k*(k - 1) - (Sum of (k-1) natural numbers) = k*(k-1) - (k-1)k/2 = k(k-1)/2

Next I need to choose any 3 multiples non repetitively and find their combinations until I have added all the k multiples.

How could I arrive at some formula that could give me the total number of combinations with k numbers right away?

-

First you choose $(k-1)$ numbers out of $k$ $${k \choose k-1}$$ Now out of the ${k \choose k-1}$ numbers you choose n of them where n is a number between 1 and ${k \choose k-1}$, You add up all the possibilities for n.

This will be the final formula $\sum_1^{k \choose k-1}{{k \choose k-1}\choose n}$

-
The last expression can be simplified to $2^{\binom{k-1}{k}}-1$ – ronno Sep 23 '13 at 4:29