3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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}$

$\endgroup$
1
  • $\begingroup$ The last expression can be simplified to $2^{\binom{k-1}{k}}-1$ $\endgroup$
    – ronno
    Sep 23, 2013 at 4:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .