Expert: Ahmed Salami - 3/2/2006

Question
Suppose there are 8 different toppings that you can choose to include or leave off of his hamburger. you can choose as few or as many toppings as you likes. How many different options do you have when building your hamburger?

Answer
Hi kevin,
The number of ways of selecting r things from a group
containing n is defined as nCr(read 'n combination r').
nCr = n!/(n-r)!r!
where n! = n(n-1)(n-2)(n-3).....(3)(2)(1)
(Note: 0! = 1)
Now, the problem we have here is to determine the number
of ways in which the combinations of toppings is
possible. Considering the possible number of toppings on
one hamburger, we could have none(assuming that is an
option), one, two and up to eight on it at the same
time.
If we are going by the first option, then the number of
ways of selecting no topping from eight would be
8C0 = 8!/8!0! = 1
The number of ways of selecting only one topping is
8C1 = 8!/7!1! = 8
In the same manner, the number of ways of selecting
r toppings from eight would be
8Cr = 8!/(8-r)!r!
To find the total number of different combinations of
toppings we can have, we add up this sums i.e
Number of combinations N
= 8C0 + 8C1 + 8C2 + 8C3 + 8C4 + 8C5 + 8C6 + 8C7 + 8C8
which could be tedious work.
We can, however, find a way to go about it easily.
Referring to the binomial distribution formula;
(x+y)^n = (nC0)(x^n)(y^0) + (nC1)(x^n-1)(y^1)
        + (nC2)(x^n-2)(y^2) + (nC3)(x^n-3)(y^3)
        +....+ (nCr)(x^n-r)(y^r) +....+ (nCn)(x^0)(y^n)
(Note that the sum of the powers of x and y always
equals n, also nCr has its usual meanings)
Let x = y = 1, then
(1+1)^n = nC0 + nC1 + nC2 + nC3 + .... + nCr + ... + nCn
And therefore,
nC0 + nC1 + nC2 + nC3 + .... + nCr + ... + nCn = 2^n
which would be a very useful relationship to us.    
Back to our problem,
N = 8C0 + 8C1 + 8C2 + 8C3 + 8C4 + 8C5 + 8C6 + 8C7 + 8C8
 = 2^8
 = 256
We therefore have 256 options regarding the different
combinations of toppings.
If there must be at least one topping on the hamburger
(i.e if you can't have a burger without topping),
we simply substract 8C0 = 1 to get
N = 255
I hope i have helped. You can always get back to me.
Regards.