Combinatorics problem using inclusion/exclusion on matching pairs There are 5 different pairs of shoes. How many ways are there for 5 people to each choose 2 shoes with no one getting a matching pair?
So I think this is a inclusion/exclusion problem.
I think that the universe $|U|=5!$
Then I'm not sure how to continue.
I guess I have to add up the number of ways for 1 person to get a matching pair. Then 2 people and so forth to all 5 people getting matching pairs.
$5! - [5C1 * 4! - 5C2 * 3! + 5C3 * 2! - 5C4 * 1! + 5C5 * 0!] = 44$
So I'm pretty sure this is wrong and the $|U|=\frac{10!}{2^5}$. However I have trouble setting up the $P_i,P_i\cap P_j,...$. 
I tried taking the number of ways that a person gets a matching pair as 
$\binom{5}{1} * \frac{8!}{2^4}$ but it doesn't work.
 A: Firstly, the universal set $U$ of all shoe distributions has cardinality
$$|U|=\frac{10!}{2!^5}$$
because there are $10$ distinct shoes to split into $5$ pairs.
Now call set $P_i$ the set of shoe distributions such that person $i$ has a matching pair, then
$$|P_i|=5\cdot \frac{8!}{2!^4}$$
because there are $5$ types of shoe for person $i$ to pick a pair from and for each the remaining $8$ shoes can be distributed to the $4$ other people in $\frac{8!}{2!^4}$ ways.
The intersection $P_{i_1}\cap P_{i_2}$ is the set of shoe distributions such that person $i_1$ and person $i_2$ both get a matching pair each hence
$$|P_{i_1}\cap P_{i_2}|=5\cdot 4\cdot\frac{6!}{2!^3}$$
because person $i_1$ can pick a shoe type for a matching pair in $5$ ways then for each of those person $i_2$ can pick a matching pair type in $4$ ways then for each the remaining $6$ shoes can be distributed in $\frac{6!}{2!^3}$ ways.
The remaining intersections are calculated in the same way.
The crucial formula here is inclusion-exclusion which says that your desired count is
$$|U|-S_1+S_2-S_3+S_4-S_5$$
where
$$S_k=\binom{5}{k}|P_{i_1}\cap P_{i_2}\cap\cdots P_{i_k}|$$
hence

$$\text{desired count}=\frac{10!}{2!^5}-\binom{5}{1}\cdot 5\cdot\frac{8!}{2!^4}+\binom{5}{2}\cdot 5\cdot 4\cdot\frac{6!}{2!^3}-\binom{5}{3}\cdot 5\cdot 4\cdot 3\cdot\frac{4!}{2!^2}+\binom{5}{4}\cdot 5\cdot 4\cdot 3\cdot 2\cdot\frac{2!}{2!^1}-\binom{5}{5}\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1\cdot\frac{0!}{2!^0}$$

