Question

Nine people sit down for dinner where there are three choices of meals. Three people order the beef meal, three order the chicken meal, and three order the fish meal. The waiter serves the nine meals in random order. Find the number of ways in which the waiter could serve the meal types to the nine people so that exactly one person receives the type of meal ordered by that person.

Answer 1

How many do you think?

Answer 2

There's probably 81 ways.

Answer 3

isnt that 216 ways?

Answer 4

If the meals were all different, there would be 9! possible order sequences. 9! = 9*8*7....

If they were identical, then the ordering would not matter.

The next thing seems to be to reduce 9! by dividing by permutations rule out by constraints. Each meal type seems to be identical, giving 3!=6 permutations to ignore per meal type so that's 18. Not much reduction there. I'm stuck!

Answer 5

From a PM from @Nurali

Call a beef meal B, a chicken meal C, and a fish meal F. Now say the nine people order meals BBBCCCFFF respectively and say that the person who receives the correct meal is the first person. We will solve for this case and then multiply by 9 to account for the 9 different ways in which the person to receive the correct meal could be picked. Note, this implies that the dishes are indistinguishable, though the people aren't. For example, two people who order chicken are separate, though if they receive fish, there is only 1 way to order them. The problem we must solve is to distribute meals BBCCCFFF to orders BBCCCFFF with no matches. The two people who ordered B's can either both get C's, both get F's, or get one C and one F. We proceed with casework. If the two B people both get C's, then the three F meals left to distribute must all go to the C people. The F people then get BBC in some order, which gives three possibilities. The indistinguishability is easier to see here, as we distribute the F meals to the C people, and there is only 1 way to order this, as all three meals are the same. If the two B people both get F's, the situation is identical to the above and three possibilities arise. If the two B people get CF in some order, then the C people must get FFB and the F people must get CCB. This gives 2 x 3 x 3 = 18 possibilities. Summing across the cases we see there are 24 possibilities, so the answer is 9x24 = 216.

Thank you for your thorough reply!

Answer 6

Wow!

Answer 7

My Pleasure.