# Combinations of up to eleven letters

How many combinations of all sizes can be formed with the first 11 letters of the alphabet, a; b; c; d; e; f; g; h; i; j; k ?

If for example abc is a solution then bac is not an additional solution.

Thanks.

-
Combinations or permutations ? – Amr Jan 2 '13 at 23:02
permutations, sorry – fosho Jan 2 '13 at 23:04
@fosho "abc" and "bac" are different permutations, so will constitute 2 different solutions, yet you say that it's not an additional solution. This is why Amr asked if you wanted combinations. – Calvin Lin Jan 2 '13 at 23:07
Sorry its late here...combinations. – fosho Jan 2 '13 at 23:08

Each letter $a$ through $k$ can either be included in the word or not included in the word, so that's two possibilities for each of the $11$ letters, for a total of $$\underbrace{2\times 2 \times \cdots \times 2}_{11 \text{ times}} = 2^{11}$$ possible words, assuming you count the "empty word" with $0$ letters.

-
+1 for the 'in-or-out' explanation. – Clive Newstead Jan 2 '13 at 23:50

If we think of possible combinations of the first eleven letters of the alphabet as subsets, then the number of combinations of your letters can be equated to the size of the powerset $\mathcal{P}(S)$ of $S =\{a, b, c, d, e, f, g, h,i, j, k\}$. That is, the number of possible combinations of the letters in $S$ is equal to the number of subsets of set $\,S\,$, (including the empty set). The size of the powerset $S$ equals $2^{|S|}$, where $|S|$ denotes the size, or cardinality, of set $S$.

Since $S$ has 11 elements, $|S| = 11$, so the number of subsets of $S$ is equal to $2^{11}$. If we exclude the empty set - which is a subset of every set (and here would represent "the combination of $0$ letters"), then we have $2^{11} - 1$ possible combinations (of all sizes $\ge 1, \le 11$) of the letters of $S$.

Put differently: We can compute

(# ways to choose 11 letters) + (# of ways to choose 10 letters) + ... + (# of ways to choose 2 letters) + (# of ways to choose 1 letter) = $$\binom{11}{11} + \binom{11}{10} + \cdots +\binom{11}{2} + \binom{11}{1} = 2^{11} - 1 = 2048 - 1 = 2047\;\;$$ possible combinations (assuming a "combination" has at least one letter, and no more than $11$.

-

If you allow a combination of size zero then $$\sum_{i=0}^{11} {11 \choose i} = 2^{11} = 2048$$ but if not then one less, i.e. $2047$.

-

This is the numbr of subsets of $\{a,b,...,k\}$ is $2^{11}$

If you don't allow the empty combinations is $2^{11}-1$

-