1
$\begingroup$

The following problem was a fun combinatorics question I encountered, there seems to be a buildup in the question, I wanted to ask if my reasoning sounds plausible. I'm sorry if my reasoning is a bit long. I enjoyed this question a lot.

This seems to be a classical problem in combinatorics: 24 persons are going to have dinner at a round table. They either order steak, or lobster. The restaurant has only 5 lobsters available, and for technical reasons this dish is only prepared for two persons at a time, who then also should sit next to each other.

$(a)$ In how many ways can $10$ lobster-eaters be selected from $24$ persons?

My answer: $\binom{24}{10}=\frac{24!}{14! 10!}$, this one is straightforward I think, we simply choose 10 out of 24, this is given by the binomial coefficient.

$(b)$ In how many ways can these $10$ lobster-eaters be divided in $5$ ordered pairs?

Now we want to permute $5$ objects out of $10$ objects which is equal to: $$ 5!\cdot \binom{10}{5}=\frac{10!}{5!}$$

(c) In how many ways can 14 steak-eaters and 5 ordered pairs of lobster-eaters be seated at a round table. For an ordered pair of lobster-eaters, the second should sit to the right of the first one. Rotated seatings are considered equal.

We have $19$ "people" (here we consider the pairs as being one, since they cannot be parted any way) in total, so there are $19!$ different arrangements for the "individuals" to sit down, however we do not make a distinction between the $19$ different cycles, we simply count them as the same, so we need to divide by 19 to count the possible arrangements the eaters can be seated at the table without overcounting.

We get that : $$\frac{19!}{19}=18!$$

Alternatively, suppose I want to sit down at the table, while nobody is watching, I sit down at the first seat. Now I automatically determine the cycle structure, I am the first person to start with, I can never be moved around and I will not get up. There are now still $18$ "people" that need to make a decision regardless of my selfish decision. This would give $18!$

(d) Finally argue that the total number of ways that the 24 people can have dinner equals:

$$ \frac{24! 18!}{14! 5!} $$

Clearly the problem is partitioned in such a way to help us answer this final question. If we first think that we need to select the lobster eaters AND that 10 people must be ordered into lobster pairs AND that we then need to sit everyone down, the answer follows by taking the product of these three combinations: $$ \frac{24!}{14! 10!} \cdot \frac{10!}{5!} \cdot 18!= \frac{24!18!}{14! 5!}$$ We observe that the $10!$ cancels and we get our desired answer.


In a fun little story solving this whole question boils down to: A large group of people arrive at a restaurant. They first decide with their group the 10 lucky individuals that want lobster, this is question (a). These $10$ then people then decide whom they want to pair up with, this is question (b), finally, everyone needs to sit down, this is question (c). The final answer in (d) results in the occurrences of all these possible combinations, this is computed by taking the product. Truly a great question!

$\endgroup$
1
$\begingroup$

Your answers to each part of the question are correct. However, your reasoning is incorrect for part (b).

We want to choose five ordered pairs of people from ten people. We can choose two of the ten people, two of the remaining eight people, two of the remaining six people, two of the remaining four people, and both of the remaining two people in $$\binom{10}{2}\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2} = \frac{10!}{2!8!} \cdot \frac{8!}{2!6!} \cdot \frac{6!}{2!4!} \cdot \frac{4!}{2!2!} \cdot \frac{2!}{2!0!} = \frac{10!}{2!2!2!2!2!}$$ ways. Since each pair must be ordered, we must multiply by the two ways we can arrange each of the five pairs, which yields $$\binom{10}{2}\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}\cdot 2^5 = 10!$$ However, the order in which the pairs are selected does not matter, so we must divide by the $5!$ orders in which the pairs could be selected, which yields $$\frac{1}{5!}\binom{10}{2}\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2} \cdot 2^5 = \frac{10!}{5!}$$

Alternatively, we can arrange the ten people in line in $10!$ ways. The first two people in line become the first ordered pair (in the order in which they appear in line), the next two people in line become the second ordered pair, and so forth. However, we would get the same set of five pairs if we were to permute the five ordered pairs within the line. For instance, the order $(3, 4), (7, 8), (1, 2), (9, 10), (5, 6)$ results in the same set of ordered pairs as $(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)$. Hence, we must divide by the $5!$ orders in which the same set of ordered pairs of people could be arranged in line, which yields $$\frac{1}{5!} \cdot 10!$$ Perhaps this is what you had in mind, but it is not clear from what you have written.

$\endgroup$
  • $\begingroup$ thank you, this is indeed what I was thinking in the back of my mind (second part) but I did know how to formulate it. $\endgroup$ – Wesley Strik Dec 7 '18 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.