One more combinatorics question

[sk381]

My friend says that : If there are 9 different toppings then the number of ways to choose toppings for one pizza is 2^9, the number of the possible subsets of the set of 9 toppings.

How can this be? Could someone explain with an example?

Sorry if this seems very trivial...

 

[sk381]

For example: for 3 toppings, ABC the possible subsets would be:

A,B,C,AB,AC,BC,ABC..and the final one is no topping at all.. making it 2^3=8 choices.

Is that correct?

 

[Werg22]

No, the number of possible toppings is 45. 9^2 takes order into account. However for this problem, order does not count; AB is the same as BA. Since there are 9 cases for which the two toppings are the same, we are left with 9^2 - 9 = 72 cases in which the two toppings aren't. However since there are 2! = 2 ways to rearrange the order of selection of two different toppings, we divide 72 by 2, which gives 36. Hence we have 36 total combinations for which the toppings are different and 9 for which they are the same, giving 45 different combinations.

 

[bel]

The class of subsets of the set \{A\} is called Power(A) and has n(Power(A)) = 2^{n(A)}. This is because the elements, in this case the toppings, are either there or not there, so 2 to the power of the number of toppings there. Hence, your second post is correct.

 

[Werg22]

Sorry, I had misunderstood the question.