1
$\begingroup$

We have n pairs of different animals (male and female from each species, so each pair is different). How many ways are to divide the $2n$ animals into $n$ different rooms, so in every room there are exactly two animals that are not from the same species? (two females and two males are allowed).

I know I should use the Inclusion exclusion principle but I don't know how... Thank you:)

$\endgroup$
1
$\begingroup$

Hint: Call $A_i=\{\text{Ways to pair them such that animals $i$ got the same room}\}$ Then you want all possible pairs minus the union of these $A_i$ i.e., $$|A\setminus \bigcup _{i=1}^n A_i|.$$ To count all possible pairings do all permutations and split them 2 by 2 but divide by $2^n$ because there is no order inside the rooms.
Can you count $A_i$? Choose a room for the $i-$th animals and scratch that room and the animals. Do the same to count all pairings but now you have $n-1$ pairs and $n-1$ rooms. What about $A_i\cap A_j$ for $i\neq j$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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