# Calculating number of possible combinations

• Oct 5th 2010, 04:02 AM
chowner
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!
• Oct 5th 2010, 04:10 AM
Plato
Quote:

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 $\displaystyle 2^N-1$
If $\displaystyle N=3$ we get $\displaystyle 2^3-1=8-1=7$
• Oct 5th 2010, 04:13 AM
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 :)
• Oct 5th 2010, 04:19 AM
Plato
Quote:

Originally Posted by chowner
Still need to wrap my head around why that formula works.

It works because $\displaystyle 2^N = \sum\limits_{k = 0}^N \binom{N}{k}$ is the total number of subsets.
Subtract 1 for the empty set.
• Oct 5th 2010, 04:32 AM
Quote:

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.