Question

There are 4 mathematicians m1;m2;m3;m4 and 4 computer scientists c1; c2; c3; c4. mi and ci are enemies for each i = 1; 2; 3; 4 (i.e. m1 and c1 are enemies, m2 and c2 are enemies etc.). By the end of part (d), we ought to know how many ways there are to line up these 8 people so that no enemies are next to each other.

(a) How many ways are there to line up the 8 people with no restriction?

(b) How many ways are there to line up the 8 people such that m1 and c1 ARE next to each other? Hint: there are 2 ways to arrange m1 and c1 between themselves. Then once we have done that, we can imagine them as “glued together". So there are now 7 objects to permute (6 people and 1 glued pair).

(c) How many ways are there to line up the 8 people so that m1 and c1 ARE next to each other AND m2 and c2 are next to each other? Hint: use the gluing idea again.

(d) For i = 1; 2; 3; 4 let Ai represent the set of permutations of the people where mi and ci are next to each other (note in part (b), you found |A1|. Use inclusion-exclusion to find the number of bad permutations |A1 U A2 U A3 U A4|. Then conclude the number of good permutations.

Answer 1