2
$\begingroup$

Say I have k students, four of them are Jack, Liz, Jenna and Tracy. I want to count the number of permutations in which Liz is standing left to Jack and Jenna is standing right to Tracy. I define $A = ${Liz is left to Jack} so $|A| = \frac{k!}{2}$. The same goes for $B$ with Jenna and Tracy.

I know that $|A \cap B| = |A| + |B| - |A \cup B|$

But how do I find the union? I'm guessing it involves inclusion-exclusion, but I can't remember how exactly.

Any ideas? Thanks!

3 Answers 3

2

Let $f \colon A \to A$ be the map that switches Jenna and Tracy. It is a ivolutive bijection and restricts to a bijection $A \cap B \to A \cap B^c$. Hence $|A \cap B| = \frac 12|A| = \frac{k!}4$.

2

The order relationship between Liz and Jack is independent of that between Jenna and Tracy. You already know that there are $k!/2$ permutations in which Liz stands to the left of Jack. In each of those Jenna can be on the right of Tracy or on her left without affecting the order of Liz and Jack, so exactly half of these $k!/2$ permutations have Jenna to the right of Tracy. The answer is therefore $k!/4$.

0

There are $\dbinom{k}{2}$ ways to choose the positions that we will ultimately put Liz and Jack into. For each such choice, there is only one way to place Liz and Jack, since Liz is to the left of Jack.

For choice we have made for Liz and Jack, there are $\dbinom{k-2}{2}$ ways to choose the positions occupied by the other two. And now there are $(k-4)!$ ways to choose the positions of the others, for a total of $\binom{k}{2}\binom{k-2}{2}(k-4)!.$