Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

3 Answers 3

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$.

share|improve this answer

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$.

share|improve this answer

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)!.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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