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 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:

1. a*b

2. b*c

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:

4. a*b + b*c

5. a*b + c*a

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:

1. a*b*c

2. b*c*d

3. c*d*a

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

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

5. a*b*c + b*c*d

6. a*b*c + c*d*a

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

8. b*c*d + c*d*a

9. b*c*d + d*a*b

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:

11. a*b*c + b*c*d + c*d*a

12. a*b*c + b*c*d + d*a*b

13. a*b*c + c*d*a + d*a*b

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.

Now I am trying with a set of k 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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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 formula $$\sum_1^{k \choose k-1}{{k \choose k-1}\choose n}$$

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

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.