Spurred by a trivia question

If you have 4 pizzas with 4 toppings each out of 18 possible pizzas, how many combinations are possible?

The answer given in a Pizza Hut commercial is 6,321,000, but I have no idea where they got that from.

By my calculations, if each topping can only be used once per pizza, and no two pizzas can be identical, the number of possibilities is:
(18C4)C4 = 3,646,049,676,885
Am I correct?

What I'd really like to know is the number of possibilities if toppings can be repeated and whole pizzas can be repeated.
I start off with (18⁴)⁴ = 18¹⁶ possibilities, but I can't recall how to correct for the many possibilities where the order the toppings are added or the arrangement of the pizzas in the box are the only differences. Anyone know?

This message has been edited. Last edited by: methos,

I can't see how Pizza Hut comes up with its number, either, methos. But I get results different from yours, too. However, I'm by no means confident I'm thinking straight on this one.

Anyhow, I would conclude these things: on the assumption, first, that no topping can be repeated on any single pizza, we can take ₁₈C₄ as the number of ways to make any one pizza. This is 3060. Thereafter, I wouldn't use combinations at all, but permutations. If no two pizzas can be alike, then there are 3060·3059·3058·3057, or 87,505,192,245,240 ways to order four pizzas. If any pizzas can be alike, the result would be instead 3060⁴, or 87,677,004,960,000.

If, instead, any topping can also be repeated, then I thought of it this way. Instead of having combinations chosen from a set of eighteen, you would effectively have a set of 72, since each topping would have to be counted up to four times. In that case, we have to find ₇₂C₄, which is 1,028,790 different single pizzas (including some with double,triple, or even quadruple hits of this or that). I would then permute each of these four ways, as above. If any two pizzas can be the same, I get 11,202,293,605,452,268,810,000, and somewhat fewer if any two pizzas have to differ in at least one topping.

I don't understand your concern about the ordering of the toppings. Since we're talking about combinations in the first instance here, the order in which toppings are added is irrelevant. As I said, though, I don't really trust this answer myself, so I'm eager to hear how someone else has looked at the problem.

To use permutations (or simple exponents) in the first example would be to assume that the order the pizzas are chosen somehow matters. The reason I chose combinations was that I decided to operate under the assumption that the order in which the pizzas are chosen doesn't matter (e.g. Kermit ordering pizza A, Miss Piggy ordering pizza B, Gonzo ordering pizza C, and Jessica ordering pizza D is considered the same under my assumptions as Kermit ordering pizza D, Miss Piggy ordering pizza C, Gonzo ordering pizza B, and Jessica ordering pizza A).

My concern about the order of toppings or pizzas wasn't with the first example because, as you say, using combinations takes care of that. My concern was with the second case (where the toppings and the pizzas could be repeated) because, starting with exponents as I proposed, you would overcount. I like the idea of using 72 and combinations rather than 18 and exponents. I think that does solve the duplication problem, but I'll have to think about it some more to convince myself. The only thing I disagree with so far is your choice to use permutations in the final step. Instead, since I am operating under the assumption that who ordered which pizza doesn't matter, I would repeat what you did with the toppings and use _{(1,028,790*4)}C₄.

With respect to the first case, methos (in which the toppings on any single pizza may not be repeated), it is pretty clear that there are 3060 ways to build one. It doesn't matter who orders what, we can still use permutations thereafter to find the total possible ways of assembling four pizzas. The first pizza may be any of 3060 choices. For each one of these, there are then 3060 or 3059 ways of choosing a second one, depending on whether two may be alike or not. If not, the problem just naturally reduces at this point to permutations. The permutations of n things taken r at a time is n(n-1)(n-2)...(n-r+1), so the permutations of 3060 things taken 4 at a time is given by₃₀₆₀P₄ = 3060(3060-1)(3060-2)(3060-3). But if any two pizzas may be identical, the answer is more simply just 3060⁴.

I read a press release by Pizza Hut about this, they claim she says "over six million topping combinations". But I saw the commercial today and she gives an exact number that sounded like six hundred thousand-something.

I also read a bunch of things picking on the commercial because they also think the number given is wrong.

Just a clarification of what I tried to say in my second post above, methos. (I add it as a postscript since my edit button has been unaccountably and rather rudely jerked out of my hands.)

Making any single pizza is a question of combinations of toppings, of course. But thereafter, permutations are involved even if ordering of choices seems to be irrelevant. Say you have four serving platters at your digs (or crib, or whatever). Your task: to fill them with four pizzas. You have any one of 3060 choices for the first (arbitrarily numbered), 3059 for the second, and so on, under the assumption the pizzas must differ pairwise. That is, you are permuting choices from a set of 3060 over four positions.

I see now that my perhaps careless choice of the word order in my first reply to your question may have been somewhat confusing. I didn't mean to say that we had to put the four pizzas in order. I meant to say that we had to put in an order for four pizzas.

Maiku, the problem is, I don't care which order the pizzas were chosen in or in which position in the box they appear. Permutations, by their nature, do 'care.'

Say I have 3 types of pizzas and want to know how many different possibilities of 3 (with no repeats) I can assemble. The answer is obviously 1, if I don't care about order. Using permutations (₃P₃), I get and answer of 6.

That is why I used combinations. In this example, ₃C₃ gives me the answer I'm looking for, 1.

The problem is, although combinations allow me to ignore order, they don't allow me to determine the possibilities if repeats are allowed. Exponents do the latter, but, like permutations, they 'care' about order.

There are 10 possibilities (I think, that's done by hand) if you have 3 types of pizza, want 3, allow repeats, and don't care about the order. 3³ = 27, almost 3 times the answer I'm looking for.

I had thought that your idea of using _n*rC_r might work there, but I now see that it would overcount as well, giving _3*3C₃ = 84.

You're right, methos. My method is obviously off. I'll rethink it and see if I can come up with anything else.

By the way, I didn't say or imply that, given three types of pizza, three to be ordered, with repeats allowed, the answer would be 84, and never suggested the formula _n·rC_r would be correct in such a case. My answer would have been 27. And if there were no repeats allowed, then my method would have given 6. Neither of these is correct, of course. Your calculation of 10 by hand is certainly right, given what I now understand better is what you meant.

I didn't mean to suggest that you suggested the last part, just that I for a moment (mistakenly) thought I might be able to apply what you had suggested to that.