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

• @N.Shales the first time i tried this I had $\frac{10!}{2^5} - [(5C1)*8!/2^4 - (5C2)*6!/2^3 + (5C3)*4!/2^2 - (5C4)*2!/2^1 + (5C5)*0!=101644]$ – HiPolyEraser Apr 11 '17 at 3:21
• You nearly had it, but I think you need to make clear in your mind what $|P_i|$ is. Where do the terms $5C1$, $5C2$ etc come from? They should be attributed to the number of ways of choosing $1,2,\ldots$ overlaps from $5$ sets, I think you have interpreted them as something else. p.s. I feel we should delete these comments soon, before they get reported as discussion. – N. Shales Apr 11 '17 at 3:29
• @N.Shales I think I have it written down as was as $5C2$ is the number of ways to take the intersection of $2P$ sets and so forth with the rest. I was interpreting it as the number of ways to pick a matching pair. – HiPolyEraser Apr 11 '17 at 3:37
• Okay, I'll just answer. I understand how this confusion can arise. – N. Shales Apr 11 '17 at 3:45

## 1 Answer

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

• (+1) This gives $65280$ – robjohn Apr 11 '17 at 4:28
• Thank you very much for explaining. – HiPolyEraser Apr 11 '17 at 4:40
• My pleasure! Thank you for the question. – N. Shales Apr 11 '17 at 9:09