Let's suppose that we have three variables: $xyz (n=3)$. We need to calculate how many unique combinations we can make. So in this case, you can simply get the answer without using any formulas: $xy, xz, yz, xyz$. So there are $4$ unique combinations. But how do you calculate it with some kind of formula when it gets more complicated? So for example, $4$ variables $wxyz$. Now you have $wx, wy, wz, xy, xz, yz, wxy, wxz, wyz, xyz, wxyz$ ($11$ combinations). And how do you do this when you have even $10$ variables? How do you do this?
[Math] How to calculate unique combinations
combinatorics
Related Solutions
For clarification, I am assuming we are keeping it as an ordered pair (A,B,C) for whatever ABC happens to be. (I.e. we are never concerned about a permutation of the letters such as (B,A,C))
You have 3 choices for the result of A, three choices for the result of B, and 3 choices for the result of C. By multiplication principle it is then $3\cdot 3\cdot 3 = 3^3=27$.
In general, if you have $r$ variables, each of which can take $n$ values, (I.e. we have letters $(A_1, A_2,\dots, A_r)$ each of which can be any number from $\{1,2,\dots,n\}$, there will be $n\cdot n\cdots n = n^r$ total possibilities.
Even more generally, if you have $r$ variables, the $i^{th}$ of which can take on $n_i$ values, you will have $\prod\limits_{i=1}^r n_i$ number of possibilities.
For a simple example, you go to an icecream shop and would like to get a sundae. A sundae consists of one flavor of icecream and any combination of toppings you'd like (some, all, or none). If there are five flavors of icecream and four available toppings, how many different ice cream sundaes are possible? Break it up via multiplication principle to first ask the question how many flavors of icecream there are (flavor 1, flavor 2,...). Then to ask the question if you use the first topping (yes or no), yes or no to the second topping, yes or no to the third...
This is exactly the same problem as how many possibilities exist for (A,B,C,D,E) if $A\in\{1,2,3,4,5\}$, and each of B through E are either 1 or 2. If for example, B is 1, then don't use that topping.
There are then $5\cdot 2\cdot 2\cdot 2\cdot 2=80$ possible sundaes.
The answer seems to have been given by @N.F.Taussig
in the question comments and formalised by @John C
.
To guarantee $m$ unique letters from groups of $n$, I need to select $\binom{n-1}{m} + 1$ combinations.
Wikipedia explains this notation to be: $\binom{g}{k} = \frac{g!}{k!(g-k)!}$
So to answer the example with $n=6$ and $m=3$:
$\binom{n-1}{m} = \binom{6-1}{3} = \binom{5}{3} = \frac{5!}{3!(5-3)!} = \frac{5!}{3!\times2!} = \frac{5\times4\times3\times2\times1}{(3\times2\times1)\times(2\times1)} = \frac{5\times4}{2\times1}$
$\binom{n-1}{m} + 1 = \frac{20}{2}+1 = 11$
And for my own real world use with $n=20$ and $m=6$:
$\binom{n-1}{m} = \binom{20-1}{6} = \binom{19}{6} = \frac{19!}{6!(19-6)!} = \frac{19!}{6!\times13!} = \frac{19\times18\times17\times16\times15\times14}{6\times5\times4\times3\times2\times1} = \frac{19,535,040}{720}$
$\binom{n-1}{m} + 1 = 27,132+1 = 27,133$
Which I must admit, is a heck of lot bigger than I expected!
Best Answer
A set with $n$ elements has exactly $2^n$ subsets. Here we do not want the empty set, nor do we want any set with exactly one element. Thus the answer is $$2^n-n-1$$