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.

Consider a set of n boys and n girls. In each situation below, use inclusion-exclusion to derive formulas for the number of ways to partition the $2n$ people into pairs so that for each $i$ the $i$-th tallest boy is not paired with the $i$-th tallest girl. (keep in summation form)

(a) Same-sex pairs allowed.

(b) No same-sex pairs allowed.

I know that the Principle of Inclusion-Exclusion states that given sets $A_1,...,A_n$ we have that

$$|\cup_{i=1}^n A_i| = \sum\limits_{S\subseteq[n]} (-1)^{|S|}|\cap_{i \in S} A_i|$$

To group $2n$ people into distinct pairs, I would have to count $$\frac{(2n)!}{2^nn!} = \prod\limits_{i=1}^n (2i-1)$$ pairs (they are equivalent statements).

I don't know how to continue from here and use the summations exactly to do both the questions.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

There is an overarching condition placed on these problems: that the $i$th tallest boy is not paired with the $i$th tallest girl.

So, first you would count how many ways you can pair off the boys and girls (either with no restrictions as in (a), or with the restrictions placed in (b)).

Then you could count in how many ways you can pair them off in which at least one of the boys is paired off with the corresponding $i$th tallest girl; you would need to subtract those from the total.

But this takes away too much; if the $i_1$th tallest boy and the $i_1$th tallest girl are paired, and the $i_2$th tallest boy is paired with the $i_2$th tallest girl, then you counted this twice, and "removed it" twice. So you should count how many ways you can have two pairs of boy-paired-with-girl-of-corresponding height, and add it back.

Then do it for three such pairs; then four; etc.

share|improve this answer
    
This is the unexpurgated version. (+1) –  robjohn Nov 2 '11 at 18:57

Hint: Let $A_i$ be all the situations that have the $i^{th}$ tallest boy with the $i^{th}$ tallest girl. Use Inclusion-Exclusion to count the number of situations that have at least one exception.

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.