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.

I have 8 distinct elements. Each set has 4 pairs from the 8 elements above. How many such distinct sets are possible?

e.g. 8 elements - 1,2,3,4,5,6,7,8 example set - 1,2;3,4;5,6;7,8 the ordering of elements in a pair is not important

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

I’m assuming that the order of pairs within a set of pairs is also irrelevant.

There are $7$ ways to choose the number to be paired with $1$. Once that pairing has been made, there are $6$ elements left, so there are $5$ ways to decide which gets paired with the smallest of the remaining numbers. After that $4$ elements remain, and there are $3$ ways to decide which gets paired with the smallest of them. The last two elements must form the fourth pair, so the total number of sets of four pairs is $7\cdot5\cdot3=105$.

Added: Alternatively, you can argue as follows. There are $\binom82$ ways to choose a pair, $\binom62$ ways to choose a pair from the remaining $6$ elements, and $\binom42$ ways to choose a pair from the $4$ elements that still remain; the last two elements will of course be the fourth pair. That’s $$\binom82\binom62\binom42=\frac{8!}{2!6!}\cdot\frac{6!}{2!4!}\cdot\frac{4!}{2!2!}=\frac{8!}{2!2!2!2!}=\frac{40320}{16}=2520\;,$$ but it takes into account the order in which the pairs are chosen. Since a given set of $4$ pairs can be chosen in $4!=24$ different orders, we have to divide by $24$ to get $\dfrac{2520}{24}=105$.

By the way, I could have saved myself some of the arithmetic in this approach:

$$\frac{8!}{2!2!2!2!4!}=\frac{8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2}{2^7\cdot3}=7\cdot5\cdot3\;.$$

share|improve this answer
add comment

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.