2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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]$ $\endgroup$ – HiPolyEraser Apr 11 '17 at 3:21
  • 1
    $\begingroup$ 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. $\endgroup$ – N. Shales Apr 11 '17 at 3:29
  • $\begingroup$ @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. $\endgroup$ – HiPolyEraser Apr 11 '17 at 3:37
  • $\begingroup$ Okay, I'll just answer. I understand how this confusion can arise. $\endgroup$ – N. Shales Apr 11 '17 at 3:45
2
$\begingroup$

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

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

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.