Four non-overlapping families dine at a restaurant together. Each family consists of one father, one mother and three children. There are five tables, which are red, blue, yellow, green and brown respectively. Every table can accommodate four people, and every person must sit at some table. How many ways are there to assign the 20 people to tables so that each child sits at the same table as at least one of his/her parents? (We do not distinguish between the four seats at the same table.)
Solution
There are 278400 ways to assign the people.
Note that each family can be partitioned in either a (4, 1) fashion (where exactly one parent sits with three children and the other is alone) or a (3, 2) fashion (where one parent sits with two children and the other sits with one).
Case 1. All families are partitioned in (4, 1) fashion.
The 4-group of each family occupies a table, and the other four parents take the remaining table. There are 2 ways to choose a parent of each family. So the number of ways is if we regard the tables as the same.
Case 2. Three families are partitioned in (4, 1) fashion and one is partitioned in (3, 2) fashion.
There are 4 ways to choose which family to be in (3, 2) fashion. The 3-group must sit with one of the three parents from another family, while the 2-group must sit with the remaining two parents. There are 2 ways to choose a parent of each family, and 3 ways to choose a child of the family in (3, 2) fashion to be put in the 2-group. So the number of ways is .
Case 3. Two families are partitioned in (4, 1) fashion and two are partitioned in (3, 2) fashion.
There are ways to choose which two families to be in (3, 2) fashion. The two 2-groups must sit together, while the 3-groups must sit with one of the two parents from the other families. There are 2 ways to choose a parent of each family, and 3 ways to choose a child of each family in (3, 2) fashion to be put in the 2-groups. So the number of ways is .
It is easy to check that no other cases are possible. Since the tables are different, there are ways to arrange the tables. Therefore the answer is