<p>A pizza shop offers nine toppings. How many different "three-topping pizzas" can be formed with the nine toppings? (Assume no topping is used twice)</p>
<p>I think the answer is 9<em>8</em>7 = 504. However, a friend asked me: why isn't it a combination of 9 choose 3? 3 ways to choose from 9 toppings... I didn't know how to justify that it wasn't, but I also don't see how to justify that it's not 9<em>8</em>7. Who can settle the score here?</p>
<p>9! / [ (9-3)! (3!) ]
= 84</p>
<p>An explanation of why it's a combination and not 9<em>8</em>7 would be helpful.</p>
<p>How did you come up with 9<em>8</em>7?</p>
<p>9 ways to choose the first topping, 8 ways to choose the second, 7 ways to choose the third...</p>
<p>Because certain combinations would end up being repeated.</p>
<p>To make things simpler, suppose there are only 3 choices of toppings. Your method would produce 3<em>2</em>1 = 6. Obviously this is incorrect because there is only 1 possible combination.</p>
<p>Obsessed, let's say we had pizza toppings A,B,C,D,E,F,G,H, and I</p>
<p>Your way would consider pizzas A, B, C and B, C, A as being DIFFERENT, when in reality, the order of the toppings does not matter, so they are the same pizza. This is why combinations works (and usually the importance of order is key in determining whether to use combinations or permutations)</p>
<p>9 choose 3 is correct.</p>
<p>9 x 8 x 7 yields the permutations of three items chosen from a set of nine. Since we don't care about the actual arrangement (or pick order) of the three toppings, we need to consider the three items chosen independent of their order.</p>
<p>Three items can be arranged in 3! = 6 ways.</p>
<p>9 x 8 x 7 overcounts the number of combinations then by a factor of 6 ... which yields (9 x 8 x 7) / 6 = 84, as previously stated.</p>