Thread: Calculating number of possible combinations

Hi,

Im sure there is an easy answer to my question, but its been a while since maths class and I cant seem to work it out in my head!

Imagine I have two objects, lets call them 'A' and 'B', what I want to do is work out a formula for the total number of possible combinations of the objects, with repeats not allowed. so... for two letters the possibilities are:

1)A
2)B
3)A+B

3 possible combinations (B+A isnt valid as its the same as A+B as far as im concerned).

and for three letters:

1)A
2)B
3)C
4)A+B
5)A+C
6)B+C
7)A+B+C

(7 combinations)

what I would ideally like would be a formula for N objects! I understad the use of factorials (n!) in similar problems, but cant quite find the way to relate it to this... Can anyone help me?

Thanks!

Originally Posted by chowner

Imagine I have two objects, lets call them 'A' and 'B', what I want to do is work out a formula for the total number of possible combinations of the objects,
what I would ideally like would be a formula for N objects!

You want the total number of non-empty subsets of a set of N elements.

That is
If we get

*brain ticks for a few seconds*

Yep thats it! Thanks Plato! Still need to wrap my head around why that formula works, but at least thats not going to be bugging me all afternoon

Originally Posted by chowner

Still need to wrap my head around why that formula works.

It works because is the total number of subsets.
Subtract 1 for the empty set.

Originally Posted by chowner

*brain ticks for a few seconds*

Yep thats it! Thanks Plato! Still need to wrap my head around why that formula works, but at least thats not going to be bugging me all afternoon

Imagine you were also allowed to select none of the objects.

For 1 object, you have 2 choices

{} {A}

For 2 objects, double the number of choices

{} {A} {B} {AB}

For 3 objects, double the number of choices

{} {A} {B} {AB} {C} {AC} {BC} {ABC}

Keep doubling, so the number of choices is a power of 2.
Then reduce it by 1 choice.