Okay, a weird topic I know but I saw a question asked in NewScientist querying whether the Domino’s Pizza claim of 1.8 billion combinations is possible. Here is the answer I am submitting:
If we have 4 options on the menu (ABCD) and choose 1 topping we have 4 unique combinations. If however we choose 2 toppings we have 6 unique combinations. As toppings in a different order are considered the same combination this means that when choosing the second topping we must choose from a sub-set of the entire menu. For example, when working out how many combinations start with A the second selection is limited to B..D, but when working out how many start with B the second selection is limited to C..D (because BA is the same combination as AB.) Domino's where I live has a menu of 21 toppings. So the valid options for the first selection when choosing 2 toppings are 1..20 (20 because we have 1 more selection to make after this), the valid options for the second selection are (first selection + 1)..21 (21 because there are no more selections to make after this.)
Not only does Domino's have 21 toppings on their menu, but you have the option of single/double which doubles the amount of options per topping, however you are only permitted a maximum of 9 toppings per pizza which brings the number of combinations down significantly.To bring the number of unique combinations back up again we have to take into account that the customer may order between 0..9 toppings, so we have to work out the iterations for each and add them together, where zero toppings is a single choice. Finally, in addition to the toppings you can choose from 3 sauces (single/double), 2 cheeses (single/double), and from 6 bases - increasing the total combinations by 6x4x6 = 144! I do not consider pizza size a “combination”.
I'm not much of a mathematician myself so I wrote a simple piece of recursive code to work out the result, which by the way is 200,407,536 - In short, the answer is "No."
And here is the source code to work it out:
1 void ButtonCompute_Click(object sender, EventArgs e)
2 {
3 long combinations = 0;
4 for (int toppingsToAdd = 1; toppingsToAdd <= 9; toppingsToAdd++)
5 combinations += CalculateCombinations(21, toppingsToAdd);
6
7 //Add one combination for "No toppings"
8 combinations++;
9
10 //Take into account the non topping variations
11 combinations = combinations
12 * 6 //Multiply by 3 sauces, single or double
13 * 4 //Multiply by 2 cheeses, single or double
14 * 6; //Multiply by 6 bases
15
16 textBox1.Text = string.Format("Combinations: {0}", combinations);
17 }
18
19 long CalculateCombinations(int toppingsAvailable, int toppingsToAdd)
20 {
21 if (toppingsToAdd == 1)
22 return toppingsAvailable * 2; //Single or double
23
24 long result = 0;
25 int toppingsToAddAfterThis = toppingsToAdd - 1;
26 checked
27 {
28 for (
29 //Start at highest value, e.g. 21 options
30 int currentChoice = toppingsAvailable;
31 //Keep enough options to fulfill the rest of the choices
32 currentChoice > toppingsToAddAfterThis;
33 currentChoice--)
34 result += CalculateCombinations(currentChoice - 1, toppingsToAddAfterThis);
35 }
36 return result;
37 }
38