Number of combinations

paulieeye

Hi folks,

Question for you.

If I have 10 letters, wats the number of possible combinations I can make out of them with any number of items counting as a combination with no repetition of the same letter in a combination and order doesnt matter , and the formula for the calculation.

e.g. I have A B C D E F G H I J

there is 10 separate letters so thats 10
then there is the 2 letter combinations AB AC AD...etc
the 3 letter combinations ABC ABD...etc

so if i had 4 the answer would be 15
A B C D = 4
AB AC AD BC BD CD = 6
ABC ACD BCD ABD = 4
ABCD = 1

Thanks alot!

Fremen

2 to the power of the number of letters minus 1, if all the letters are different.

To see this, imagine all your letters, together with the word "yes" or "no" beside them. We're going to use this to represent a particular combination of letters.

A - yes
B - no
C - yes
D - yes
E - no

This corresponds to the collection ACD. With a little thought, you can see that the set of all combinations of "yes"es and "no"s corresponds to all possible collections of your letters.

There are two possibilities for each letter, so that makes 2x2x2x2x2 for five letters, or two to the power of ten for ten letters.

The set that corresponds to all "no"s doesn't have any letters in it, so you need to subtract one from your total (unless you decide that the empty set counts too).

(Most CS courses and the leaving cert teach this proof by induction, which is moronic imho. Better to put the subsets in bijection with binary representations of the integers)

bnt

You missed one possible combination there: the "null" combination of no letters at all " ". That makes 16 in total, and 16 is 2 to the power of 4 (2^4), and that's not a coincidence.

What you have there is essentially a binary table, in which each letter is either on or off. In computing terminology, you assign a 1 or a 0 to a binary register for each letter, so you'd have something like this:

A | B | C | D |String
-----------------------
0 | 0 | 0 | 0 |  
0 | 0 | 0 | 1 |    D
0 | 0 | 1 | 0 |   C
0 | 0 | 1 | 1 |   CD
0 | 1 | 0 | 0 |  B
0 | 1 | 0 | 1 |  B D
0 | 1 | 1 | 0 |  BC
0 | 1 | 1 | 1 |  BCD
1 | 0 | 0 | 0 | A 
1 | 0 | 0 | 1 | A  D
1 | 0 | 1 | 0 | A C
1 | 0 | 1 | 1 | A CD
1 | 1 | 0 | 0 | AB
1 | 1 | 0 | 1 | AB D
1 | 1 | 1 | 0 | ABC
1 | 1 | 1 | 1 | ABCD 

If you follow the same logic for n letters, you have 2^n possible combinations. If you exclude the "null" result, it's 2^n-1

paulieeye

sweet..didnt think of it like a binary table..very nice!

Yakuza

Google "Pascal's Triangle". The 10th row of that will give you the breakdown of 10-letter, 9-letter, 8-letter combinations etc (down to the 0-letter). As the others have pointed out, what you have is analagous to a binomial distribution, with a letter having a 50% probability of being included (a success, in binomial parlance).